제출 #918295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918295		amirhoseinfar1385	Cloud Computing (CEOI18_clo)	C++17	100 / 100	1038 ms	2388 KiB

clo

#include<bits/stdc++.h>
using namespace std;
struct noe{
	long long ci,fi,vi;
};
const int maxa=100000+5,maxn=2000;
long long n,m,dp[2][maxa],inf=1e15;
vector<noe>alln,allm;
bool cmp(pair<int,pair<int,int>> a,pair<int,pair<int,int>> b){
	if(a.first==b.first){
		return a.second.first<b.second.first;
	}
	return a.first<b.first;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	alln.resize(n+1);
	for(int i=0;i<2;i++){
		for(int j=0;j<maxa;j++){
			dp[i][j]=-inf;
		}
	}
	for(int i=0;i<n;i++){
		cin>>alln[i].ci>>alln[i].fi>>alln[i].vi;
	}
	cin>>m;
	allm.resize(m+1);
	for(int i=0;i<m;i++){
		cin>>allm[i].ci>>allm[i].fi>>allm[i].vi;
	}
	vector<pair<int,pair<int,int>>>fake;
	for(int i=0;i<n;i++){
		fake.push_back(make_pair(alln[i].fi,make_pair(2,i)));
	}
	for(int i=0;i<m;i++){
		fake.push_back(make_pair(allm[i].fi,make_pair(1,i)));
	}
	dp[1][0]=0;
	sort(fake.begin(),fake.end(),cmp);
	for(int i=(int)fake.size()-1;i>=0;i--){
		swap(dp[1],dp[0]);
	//	cout<<fake[i].first<<"\n";
		for(int j=0;j<maxa;j++){
			dp[1][j]=-inf;
		}
		if(fake[i].second.first==1){
			int ind=fake[i].second.second;
			for(int j=0;j<maxa;j++){
				if(j<allm[ind].ci){
					dp[1][j]=max(dp[1][j],dp[0][j]);
					continue;
				}
				dp[1][j]=max(dp[1][j],dp[0][j]);
				dp[1][j-allm[ind].ci]=max(dp[1][j-allm[ind].ci],dp[0][j]+allm[ind].vi);
			}
		}
		else{
			int ind=fake[i].second.second;
			for(int j=0;j<maxa;j++){
				if(j+alln[ind].ci>=maxa){
					dp[1][j]=max(dp[1][j],dp[0][j]);
					continue;
				}
				dp[1][j]=max(dp[1][j],dp[0][j]);
				dp[1][j+alln[ind].ci]=max(dp[1][j+alln[ind].ci],dp[0][j]-alln[ind].vi);
			}
		}
	}
	long long res=0;
	for(int i=0;i<maxa;i++){
		res=max(res,dp[1][i]);
	}
	cout<<res<<"\n";
}

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