/*raghav0307 - Raghav Gupta*/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define int ll
struct Item{
int c, f, v, prod;
Item (int cc, int ff, int vv, int type) :
c(cc), f(ff), v(vv), prod(type) {}
};
bool custom(Item a, Item b){
if(a.f < b.f)
return false;
if(a.f > b.f)
return true;
if(a.prod == 1)
return true;
return false;
}
vector<Item> v;
const int MAXN = 2e3 + 5;
const int MAXC = 50;
const int inf = 1e15;
int dp[MAXN*MAXC], dp2[MAXN*MAXC];
// int memo[MAXN + 500][800];
// int dp(int pos, int left){
// if(pos == v.size()) return 0;
// if(memo[pos][left] != -1) return memo[pos][left];
// if(v[pos].prod == 1){
// if(left + v[pos].c >= 800) memo[pos][left] = dp(pos + 1, left);
// return memo[pos][left] = max( dp(pos+1, left + v[pos].c) - v[pos].v, dp(pos+1, left));
// }
// else if(v[pos].prod == 2){
// if(v[pos].c <= left) return memo[pos][left] = max(dp(pos + 1, left - v[pos].c) + v[pos].v, dp(pos +1 , left));
// return memo[pos][left] = dp(pos + 1, left);
// }
// }
signed main(){
fast_io();
// memset(memo, -1, sizeof(memo));
int n; cin >> n;
for(int i = 0; i < n; i++){
int c, f, vv;
cin >> c >> f >> vv;
v.push_back(Item(c, f, vv, 1));
}
int m; cin >> m;
for(int i = 0; i < m; i++){
int c, f, vv;
cin >> c >> f >> vv;
v.push_back(Item(c, f, vv, 2));
}
sort(v.begin(), v.end(), custom);
// for(auto x : v){
// cout << x.c << " " << x.f << " " << x.v << " " << x.prod << "\n";
// }
for(int i = 0; i < MAXN*MAXC; i++) dp[i] = 0;
if(v.back().prod == 2){
for(int i = v.back().c; i <= MAXN*MAXC; i++){
dp[i] = v.back().v;
}
}
// for(int i = 0; i < 25; i++){
// cout << dp[i] << " ";
// }cout << "\n";
for(int i = n+m-2; i >= 0; i--){
for(int j = MAXN*MAXC-1; j >= 0; j--){
if(v[i].prod == 1 and j + v[i].c < MAXN*MAXC){
dp2[j] = max(dp[j + v[i].c] - v[i].v, dp2[j]);
dp2[j] = max(dp2[j], dp[j]);
}
else if(v[i].prod == 2 and j >= v[i].c){
dp2[j] = max(dp[j - v[i].c] + v[i].v, dp2[j]);
dp2[j] = max(dp2[j], dp[j]);
}
}
for(int i = 0; i < MAXC*MAXN; i++)
dp[i] = dp2[i];
// for(int i = 0; i < 25; i++){
// cout << dp[i] << " ";
// }cout << "\n";
}
cout << max(dp[0], 0ll) << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1920 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
47 ms |
1960 KB |
Output is correct |
| 3 |
Runtime error |
4 ms |
2176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
