제출 #580386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580386		amunduzbaev	Cloud Computing (CEOI18_clo)	C++17	18 / 100	1673 ms	3632 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++){
			for(int k=1;k<=M;k++){
				dp[cur][j][M] = max(dp[cur][j][M], dp[cur][j][M + k]);
			}
			
			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){
					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){
					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;
				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){
							//~ cout<<i + 1<<" "<<j<<" "<<k + a[i][0]<<endl;
							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 && j < m){
					assert(i < n);
					dp[cur][j + 1][k + M] = max(dp[cur][j + 1][k + M], dp[cur][j][k + M]);
					if(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


*/

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