oj.uz

Submission #580308

# Submission time Handle Problem Language Result Execution time Memory
580308 2022-06-21T05:03:19 Z amunduzbaev Global Warming (CEOI18_glo) C++17
0 / 100
 433 ms 217132 KB 
#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;
				if(k < 0 && j < m){
					assert(j < m);
					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 && i < n){
					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){
							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 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 207668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 207668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 207668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 430 ms 217132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 385 ms 210008 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 433 ms 212364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 207668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -