Submission #1191285

#TimeUsernameProblemLanguageResultExecution timeMemory
1191285boclobanchatCloud Computing (CEOI18_clo)C++20
100 / 100
258 ms1356 KiB
#include<bits/stdc++.h>
using namespace std;
struct node { int c,f,v; };
bool comp(node a,node b) { return a.f>b.f; }
const int MAXN=2024;
const long long INF=1e18;
long long dp[MAXN*55];
node A[MAXN],B[MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i].c>>A[i].f>>A[i].v;
	int m;
	cin>>m;
	for(int i=1;i<=m;i++) cin>>B[i].c>>B[i].f>>B[i].v;
	sort(A+1,A+n+1,comp);
	sort(B+1,B+m+1,comp);
	for(int i=1;i<=n*55;i++) dp[i]=-INF;
	int r=1;
	for(int i=1;i<=m;i++)
	{
		while(r<=n&&A[r].f>=B[i].f)
		{
			for(int j=n*55-A[r].c;j+1;j--) dp[j+A[r].c]=max(dp[j+A[r].c],dp[j]-A[r].v);
			r++;
		}
		for(int j=0;j<=n*55-B[i].c;j++) dp[j]=max(dp[j],dp[j+B[i].c]+B[i].v);
	}
	long long ans=0;
	for(int i=0;i<=n*55;i++) ans=max(ans,dp[i]);
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...