Submission #580402

#	Time	Username	Problem	Language	Result	Execution time	Memory
580402		amunduzbaev	Cloud Computing (CEOI18_clo)	C++17	100 / 100	2629 ms	3640 KiB

clo

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int inf = -1e18;
const int N = 2005;
const int M = 51;
const int H = 103;
int dp[2][N][H];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 3>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	} sort(a.begin(), a.end(), [&](auto& a, auto& b){
		return a[1] < b[1];
	});
	int m; cin>>m;
	vector<ar<int, 3>> b(m);
	for(int i=0;i<m;i++){
		cin>>b[i][0]>>b[i][1]>>b[i][2];
	} sort(b.begin(), b.end(), [&](auto& a, auto& b){
		return a[1] < b[1];
	});
	
	memset(dp, -63, sizeof dp);
	dp[0][0][M] = 0;
	
	for(int i=0;i<=n;i++){
		int cur = i & 1, nxt = !cur;
		memset(dp[nxt], -63, sizeof dp[nxt]);
		for(int j=0;j<=m;j++){
			if(dp[cur][j][M] > inf){
				//~ cout<<i<<" "<<j<<" "<<0<<" "<<dp[cur][j][M]<<endl;
				if(i < n) dp[nxt][j][M] = max(dp[nxt][j][M], dp[cur][j][M]);
				if(j < m) dp[cur][j + 1][M] = max(dp[cur][j + 1][M], dp[cur][j][M]);
				if(i < n){
					//~ cout<<dp[cur][j][M + a[i][0]]<<endl;
					dp[cur][j][M + a[i][0]] = max(dp[cur][j][M + a[i][0]], dp[cur][j][M] - a[i][2]);
					//~ cout<<dp[cur][j][M + a[i][0]]<<endl;
				} if(j < m){
					assert(j < m);
					dp[cur][j][M - b[j][0]] = max(dp[cur][j][M - b[j][0]], dp[cur][j][M] + b[j][2]);
				}
			}
			
			for(int k=-M;k<=M;k++){
				if(dp[cur][j][k + M] <= inf || !k) continue;
				//~ cout<<i<<" "<<j<<" "<<k<<" "<<dp[cur][j][k + M]<<endl;
				if(k < 0 && i < n){
					assert(j < m);
					dp[nxt][j][k + M] = max(dp[nxt][j][k + M], dp[cur][j][k + M]);
					if(b[j][1] <= a[i][1]){
						if(k + a[i][0] < 0){
							dp[nxt][j][k + a[i][0] + M] = max(dp[nxt][j][k + a[i][0] + M], dp[cur][j][k + M] - a[i][2]);
						} else if(k + a[i][0] == 0){
							dp[nxt][j + 1][M] = max(dp[nxt][j + 1][M], dp[cur][j][k + M] - a[i][2]);
						} else {
							dp[cur][j + 1][k + a[i][0] + M] = max(dp[cur][j + 1][k + a[i][0] + M], dp[cur][j][k + M] - a[i][2]);
						}
					}
				} if(k > 0){
					assert(i < n);
					if(j < m) dp[cur][j + 1][k + M] = max(dp[cur][j + 1][k + M], dp[cur][j][k + M]);
					dp[nxt][j][M] = max(dp[nxt][j][M], dp[cur][j][k + M]);
					if(j < m && b[j][1] <= a[i][1]){
						if(k - b[j][0] < 0){
							//~ cout<<i + 1<<" "<<j<<" "<<k - b[j][0]<<endl;
							dp[nxt][j][k - b[j][0] + M] = max(dp[nxt][j][k - b[j][0] + M], dp[cur][j][k + M] + b[j][2]);
						} else if(k - b[j][0] == 0){
							dp[nxt][j + 1][M] = max(dp[nxt][j + 1][M], dp[cur][j][k + M] + b[j][2]);
						} else {
							dp[cur][j + 1][k - b[j][0] + M] = max(dp[cur][j + 1][k - b[j][0] + M], dp[cur][j][k + M] + b[j][2]);
						}
					}
				} 
			}
			
		}
	}
	
	int res = inf;
	for(int i=M;i<H;i++){
		res = max(res, dp[n&1][m][i]);
	}
	
	cout<<res<<"\n";
}

/*

5
6 1 6
4 1 12
5 1 5
4 1 9
6 1 12
4
6 1 9
5 1 12
6 1 6
5 1 7

3
6 1 8
6 1 5
6 1 11
3
6 1 9
6 1 4
4 1 12

*/

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