Submission #129085

#	Time	Username	Problem	Language	Result	Execution time	Memory
129085		mraron	Cloud Computing (CEOI18_clo)	C++14	54 / 100	146 ms	860 KiB

clo

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1LL<<60;
const ll mxc=21000;
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[2][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)&1]) i=-inf;
	dp[(n+m)&1][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&1][j]=dp[(i+1)&1][j];
			if(j-lst[i].c>=0 && j-lst[i].c<=mxc) {
				if(dp[i&1][j]>=-inf/2)
					dp[i&1][j]=max(dp[i&1][j], dp[(i+1)&1][j-lst[i].c]+lst[i].v);
				else
					dp[i&1][j]=dp[(i+1)&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;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10