Submission #1149732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149732		SSSM	Cloud Computing (CEOI18_clo)	C++20	100 / 100	412 ms	2136 KiB

clo

#include <bits/stdc++.h>
#if defined(__GNUC__)
#pragma GCC optimize ("Ofast")
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000010000LL;
const int mod = 1000000007;
const int MAXN = 2010, LOG=20;

struct SERVER{
	ll c, f, v, typ;
	bool operator <(SERVER M){
		if (f==M.f) return typ<M.typ;
		return f>M.f;
	}
} A[MAXN*2];

ll n, m, k, u, v, x, y, t, c, f, ans;
ll dp[2][MAXN*50];

inline void upd(ll &x, ll y){
	x=max(x, y);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n;
	for (int i=1; i<=n; i++){
		cin>>c>>f>>v;
		A[i]={c, f, v, 0};
	}
	cin>>m;
	for (int i=1; i<=m; i++){
		cin>>c>>f>>v;
		A[i+n]={c, f, v, 1};
	}
	
	sort(A+1, A+n+m+1);
	
	memset(dp, -63, sizeof(dp));
	dp[0][0]=0;
	int prev=0, curr=1;
	for (int i=1; i<=n+m; i++){
		for (int j=0; j<=n*50; j++){
			dp[curr][j]=-INF;
			//upd(dp[curr][j], dp[curr][j+1]); // optional
			upd(dp[curr][j], dp[prev][j]);
			if (A[i].typ) upd(dp[curr][j], dp[prev][j+A[i].c] + A[i].v);
			else if (j>=A[i].c) upd(dp[curr][j], dp[prev][j-A[i].c] - A[i].v);
		}
		swap(prev, curr);
	}
		
	for (int i=0; i<=n*50; i++) ans=max(ans, dp[prev][i]);
	cout<<ans<<'\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