/*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[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";
// }
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:50:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
16000 KB |
Output is correct |
2 |
Correct |
13 ms |
15972 KB |
Output is correct |
3 |
Correct |
13 ms |
16044 KB |
Output is correct |
4 |
Correct |
15 ms |
16000 KB |
Output is correct |
5 |
Correct |
19 ms |
16248 KB |
Output is correct |
6 |
Correct |
15 ms |
16256 KB |
Output is correct |
7 |
Correct |
23 ms |
16256 KB |
Output is correct |
8 |
Correct |
24 ms |
16256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
16000 KB |
Output is correct |
2 |
Correct |
13 ms |
15972 KB |
Output is correct |
3 |
Correct |
16 ms |
16000 KB |
Output is correct |
4 |
Correct |
13 ms |
16000 KB |
Output is correct |
5 |
Correct |
24 ms |
16128 KB |
Output is correct |
6 |
Correct |
25 ms |
16128 KB |
Output is correct |
7 |
Correct |
38 ms |
16364 KB |
Output is correct |
8 |
Correct |
42 ms |
16256 KB |
Output is correct |
9 |
Runtime error |
80 ms |
32452 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
15972 KB |
Output is correct |
2 |
Correct |
14 ms |
16000 KB |
Output is correct |
3 |
Correct |
14 ms |
16000 KB |
Output is correct |
4 |
Correct |
13 ms |
15984 KB |
Output is correct |
5 |
Correct |
14 ms |
16000 KB |
Output is correct |
6 |
Correct |
14 ms |
16100 KB |
Output is correct |
7 |
Correct |
15 ms |
16000 KB |
Output is correct |
8 |
Correct |
15 ms |
16100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
16024 KB |
Output is correct |
2 |
Correct |
13 ms |
16000 KB |
Output is correct |
3 |
Runtime error |
70 ms |
32312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
16092 KB |
Output is correct |
2 |
Correct |
14 ms |
16000 KB |
Output is correct |
3 |
Incorrect |
23 ms |
16128 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
16000 KB |
Output is correct |
2 |
Correct |
13 ms |
15972 KB |
Output is correct |
3 |
Correct |
13 ms |
16044 KB |
Output is correct |
4 |
Correct |
15 ms |
16000 KB |
Output is correct |
5 |
Correct |
19 ms |
16248 KB |
Output is correct |
6 |
Correct |
15 ms |
16256 KB |
Output is correct |
7 |
Correct |
23 ms |
16256 KB |
Output is correct |
8 |
Correct |
24 ms |
16256 KB |
Output is correct |
9 |
Correct |
13 ms |
16000 KB |
Output is correct |
10 |
Correct |
13 ms |
15972 KB |
Output is correct |
11 |
Correct |
16 ms |
16000 KB |
Output is correct |
12 |
Correct |
13 ms |
16000 KB |
Output is correct |
13 |
Correct |
24 ms |
16128 KB |
Output is correct |
14 |
Correct |
25 ms |
16128 KB |
Output is correct |
15 |
Correct |
38 ms |
16364 KB |
Output is correct |
16 |
Correct |
42 ms |
16256 KB |
Output is correct |
17 |
Runtime error |
80 ms |
32452 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |