思路： 考虑把询问离线 按照m排序 物品按照a排序 f[i]表示c[j]的和到i b的最大值 背包就好 O(nk)竟然能过……
//By SiriusRen #include <cstdio> #include <algorithm> using namespace std; const int N=1005; struct Ask{int m,k,s,id;}ask[N*N]; struct Node{int a,b,c;}node[N]; bool cmp(Ask a,Ask b){return a.m<b.m;} bool Cmp(Node a,Node b){return a.a<b.a;} int n,q,a[N],b[N],c[N],jy=1,ans[N*N],f[N*101]; void update(int x){for(int i=N*100-node[x].c;i>=0;i--)f[i+node[x].c]=max(f[i+node[x].c],min(f[i],node[x].b));} int main(){ scanf("%d",&n),f[0]=0x3f3f3f3f; for(int i=1;i<=n;i++)scanf("%d%d%d",&node[i].c,&node[i].a,&node[i].b); scanf("%d",&q); for(int i=1;i<=q;i++)scanf("%d%d%d",&ask[i].m,&ask[i].k,&ask[i].s),ask[i].id=i; sort(ask+1,ask+1+q,cmp),sort(node+1,node+1+n,Cmp); for(int i=1;i<=q;i++){ while(jy<=n&&node[jy].a<=ask[i].m)update(jy),jy++; ans[ask[i].id]=(f[ask[i].k]>(ask[i].m+ask[i].s)?1:0); } for(int i=1;i<=q;i++)puts(ans[i]?"TAK":"NIE"); }