题目:
题解:
首先不考虑\(b_i > m + s\)的限制。
只考虑\(a_i \leq m\)的限制.
可以发现可以将所有的询问按照\(m\)排序,所有的物品按照\(a\)排序。
这样每次只会不断的加入物品,设\(f_i\)表示能否凑出\(i\)即可.
然后加上\(b_i > m+s\)的限制.
那么我们改一下原来的定义.
我们重定义: \(f_i\)表示所有凑出\(i\)的方案中使用的所有物品的\(b\)的最小值最大的方案下那个最大的\(b\)的最小值.
这样我们拿\(f_k\)和询问的\(m+s\)比较一下即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 1024;
const int maxq = 1000010;
struct Node{
int a,b,c;
bool friend operator < (const Node &a,const Node &b){
return a.a < b.a;
}
}seq[maxq];
struct query{
int m,k,s,id;
bool friend operator < (const query &a,const query &b){
return a.m < b.m;
}
}qer[maxq];
int f[maxq],mk = 0;
inline void insert(const Node &a){
per(i,mk,a.c){
f[i] = max(f[i],min(f[i-a.c],a.b));
}
}
bool ans[maxq];
int main(){
memset(f,-1,sizeof f);
memset(ans,false,sizeof ans);
int n;read(n);
f[0] = 2000000001;
rep(i,1,n) read(seq[i].c),read(seq[i].a),read(seq[i].b);
int q;read(q);
rep(i,1,q){
read(qer[i].m);read(qer[i].k);
read(qer[i].s);qer[i].id = i;
mk = max(mk,qer[i].k);
}
sort(seq+1,seq+n+1);sort(qer+1,qer+q+1);
int p = 1;
rep(i,1,q){
while(p <= n && seq[p].a <= qer[i].m) insert(seq[p++]);
if(f[qer[i].k] > qer[i].m+qer[i].s) ans[qer[i].id] = true;
}
rep(i,1,q) puts(ans[i] ? "TAK" : "NIE");
return 0;
}