| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1273804 | mahersefo | Cloud Computing (CEOI18_clo) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define ll long long
#define all(a) (a).begin() , (a).end()
#define endl '\n'
using namespace std;
void readFromFile(string input = "input.txt",string output="output.txt") {
#ifndef ONLINE_JUDGE
freopen(input.c_str(),"r",stdin);
freopen(output.c_str(),"w",stdout);
#endif
}
const int N = 2e3+1;
#define ty array<int,4>
ty a[2*N];
int n,m,t;
ll memo[2*N][50*N];
bool vis[2*N][50*N];
ll dp(int i,int core) {
// cout << i << ' ' << core << ' ' << a[i][3] << endl;
if(i == t) {
return core ? -1e18 : 0;
}
ll &ret = memo[i][core];
if(vis[i][core]) {
return ret;
}
vis[i][core] = 1;
ret = dp(i+1 , core);
if(a[i][3] && core) {
ret = max(ret , dp(i+1 , max(0 , core-a[i][0])) - a[i][2]);
}
if(!a[i][3]) {
ret = max(ret , dp(i+1 , core + a[i][0]) + a[i][2]);
}
return ret;
}
void solve() {
cin >> n;
for(int i = 0 ; i < n ; i++) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][3] = 1;
}
cin >> m;
for(int i = n ; i < m+n ; i++) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][3] = 0;
}
t = n+m;
sort(a,a+t,[&](ty x,ty y) {
if(x[1] != y[1]) return x[1] < y[1];
return x[3] < y[3];
});
// for(int i = 0 ; i < t ; i++) {
// cout << a[i][0] << ' ' << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
// }
cout << dp(0,0) << endl;
}
int32_t main() {
readFromFile();
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
for(int i = 0 ; i < t ; i++) {
solve();
}
}