제출 #580301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580301		amunduzbaev	Cloud Computing (CEOI18_clo)	C++17	18 / 100	230 ms	3584 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];
	});
	
	//~ for(auto x : a) cout<<x[0]<<" "<<x[1]<<" "<<x[2]<<"\n";
	//~ cout<<endl;
	//~ for(auto x : b) cout<<x[0]<<" "<<x[1]<<" "<<x[2]<<"\n";
	//~ cout<<endl;
	memset(dp, -63, sizeof dp);
	dp[0][0][M] = 0;
	
	for(int i=0;i<=n;i++){
		//~ cout<<i<<endl;
		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){
				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){
					dp[cur][j][M + a[i][0]] = max(dp[cur][j][M + a[i][0]], dp[cur][j][M] - a[i][2]);
				} if(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) continue;
				//~ cout<<i<<" "<<j<<" "<<k<<" "<<dp[cur][j][k + M]<<endl;
				if(k < 0){
					if(i < n){
						dp[nxt][j][k + M] = max(dp[nxt][j][k + M], dp[cur][j][k + M]);
					}
					if(i < n && 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){
					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){
							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]);
						} 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";
}

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