Submission #129174

#	Time	Username	Problem	Language	Result	Execution time	Memory
129174		mraron	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2664 ms	2168 KiB

clo

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1LL<<50;
const ll mxc=101000;
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!=mxc) dp[i&1][j]=max(dp[i&1][j], dp[i&1][j+1]);
			
			if(j-lst[i].c>=0 && j-lst[i].c<=mxc) {
				dp[i&1][j]=max(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];
	}
	
	cout<<dp[0][0]<<"\n";
	
	return 0;
}

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