/*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;
int memo[2*MAXN][2*MAXN];
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){
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";
// }
cout << max(dp(0, 0), 0ll) << "\n";
return 0;
}
Compilation message
clo.cpp: In function 'll dp(ll, ll)':
clo.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos == v.size()) return 0;
~~~~^~~~~~~~~~~
clo.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
126160 KB |
Output is correct |
2 |
Correct |
92 ms |
126200 KB |
Output is correct |
3 |
Correct |
95 ms |
126276 KB |
Output is correct |
4 |
Correct |
95 ms |
126216 KB |
Output is correct |
5 |
Correct |
101 ms |
126456 KB |
Output is correct |
6 |
Correct |
99 ms |
126584 KB |
Output is correct |
7 |
Correct |
107 ms |
126520 KB |
Output is correct |
8 |
Correct |
107 ms |
126520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
97 ms |
126148 KB |
Output is correct |
2 |
Correct |
94 ms |
126216 KB |
Output is correct |
3 |
Correct |
93 ms |
126344 KB |
Output is correct |
4 |
Correct |
95 ms |
126208 KB |
Output is correct |
5 |
Correct |
157 ms |
126360 KB |
Output is correct |
6 |
Correct |
108 ms |
126300 KB |
Output is correct |
7 |
Correct |
237 ms |
126516 KB |
Output is correct |
8 |
Correct |
193 ms |
126396 KB |
Output is correct |
9 |
Runtime error |
400 ms |
252824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
126200 KB |
Output is correct |
2 |
Correct |
97 ms |
126188 KB |
Output is correct |
3 |
Correct |
98 ms |
126232 KB |
Output is correct |
4 |
Correct |
96 ms |
126164 KB |
Output is correct |
5 |
Correct |
100 ms |
126280 KB |
Output is correct |
6 |
Correct |
99 ms |
126200 KB |
Output is correct |
7 |
Correct |
102 ms |
126300 KB |
Output is correct |
8 |
Correct |
96 ms |
126312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
126168 KB |
Output is correct |
2 |
Correct |
94 ms |
126172 KB |
Output is correct |
3 |
Runtime error |
425 ms |
252928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
94 ms |
126300 KB |
Output is correct |
2 |
Correct |
95 ms |
126244 KB |
Output is correct |
3 |
Correct |
150 ms |
126328 KB |
Output is correct |
4 |
Correct |
175 ms |
126420 KB |
Output is correct |
5 |
Correct |
381 ms |
126752 KB |
Output is correct |
6 |
Runtime error |
267 ms |
253028 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
126160 KB |
Output is correct |
2 |
Correct |
92 ms |
126200 KB |
Output is correct |
3 |
Correct |
95 ms |
126276 KB |
Output is correct |
4 |
Correct |
95 ms |
126216 KB |
Output is correct |
5 |
Correct |
101 ms |
126456 KB |
Output is correct |
6 |
Correct |
99 ms |
126584 KB |
Output is correct |
7 |
Correct |
107 ms |
126520 KB |
Output is correct |
8 |
Correct |
107 ms |
126520 KB |
Output is correct |
9 |
Correct |
97 ms |
126148 KB |
Output is correct |
10 |
Correct |
94 ms |
126216 KB |
Output is correct |
11 |
Correct |
93 ms |
126344 KB |
Output is correct |
12 |
Correct |
95 ms |
126208 KB |
Output is correct |
13 |
Correct |
157 ms |
126360 KB |
Output is correct |
14 |
Correct |
108 ms |
126300 KB |
Output is correct |
15 |
Correct |
237 ms |
126516 KB |
Output is correct |
16 |
Correct |
193 ms |
126396 KB |
Output is correct |
17 |
Runtime error |
400 ms |
252824 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |