Submission #129080

#TimeUsernameProblemLanguageResultExecution timeMemory
129080mraronCloud Computing (CEOI18_clo)C++14
54 / 100
257 ms262148 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1LL<<60;
const ll mxc=10000;
struct dat {
	ll c,f,v;
	bool operator<(const dat& masik) const {
		if(f==masik.f) return c<masik.c;
		return f<masik.f;
	}
};
ll dp[4001][mxc+1];
int main() {
	int n,m;
	cin>>n;
	vector<dat> lst(n);
	for(int i=0;i<n;++i) {
		cin>>lst[i].c>>lst[i].f>>lst[i].v;
		lst[i].v=-lst[i].v;
	}
	cin>>m;
	lst.resize(n+m);
	for(int i=n;i<n+m;++i) {
		cin>>lst[i].c>>lst[i].f>>lst[i].v;
		lst[i].c=-lst[i].c;
	}
	sort(lst.begin(),lst.end());
	
	for(auto& i:dp[n+m]) i=-inf;
	dp[n+m][0]=0;
	
	for(int i=n+m-1;i>=0;i--) {
		//cerr<<lst[i].c<<"\n";
		for(int j=mxc;j>=0;j--) {
			dp[i][j]=dp[i+1][j];
			if(j-lst[i].c>=0 && j-lst[i].c<=mxc) {
				if(dp[i][j]>=-inf/2)
					dp[i][j]=max(dp[i][j], dp[i+1][j-lst[i].c]+lst[i].v);
				else
					dp[i][j]=dp[i+1][j-lst[i].c]+lst[i].v;
			}
		}
		//for(int j=0;j<=mxc;++j) cerr<<dp[i][j]<<" \n"[j==mxc];
	}
	
	ll ans=-inf;
	for(int i=0;i<=mxc;++i) ans=max(ans, dp[0][i]);
	cout<<ans<<"\n";
	
	return 0;
}
#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...