12分求助
查看原帖
12分求助
464562
_zys_楼主2023/7/21 09:51
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e3 + 10, M = 1e6 + 10;
const int INF = 0x3f3f3f3f;

int f[M], n, p;
bool ans[M];

struct Node
{
	int a, b, c;
}nodes[N];

struct Queries
{
	int m, k, s, id;
}q[M];

bool cmp1(Node a, Node b)
{
	return a.a < b.a;
}

bool cmp2(Queries a, Queries b)
{
	return a.m < b.m;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ )
		scanf("%d%d%d", &nodes[i].c, &nodes[i].a, &nodes[i].b);
	
	sort(nodes + 1, nodes + 1 + n, cmp1);
	
	scanf("%d", &p);
	
	for (int i = 1; i <= p; i ++ )
	{
		scanf("%d%d%d", &q[i].m, &q[i].k, &q[i].s);
		q[i].id = i;
	}
		
	sort(q + 1, q + p + 1, cmp2);
	
	int pos = 1;
	f[0] = INF;
	for (int i = 1; i <= p; i ++ )
	{
		while(pos <= n && nodes[pos].a <= q[i].m)
		{
			for (int j = 100000; j >= nodes[pos].c; j -- )
				f[j] = max(f[j], min(f[j - nodes[pos].c], nodes[pos].b));
			pos ++;
		}
		if (f[q[i].k] > q[i].m + q[i].s) ans[q[i].id] = 1;
	}
		
	for (int i = 1; i <= p; i ++ )
	{
		if (ans[i]) puts("TAK");
		else puts("NTE");
	}
	
	return 0;
}
2023/7/21 09:51
加载中...