#include <bits/stdc++.h>
#define N 2010
using namespace std;
typedef long long ll;
struct S
{
int val, c, f, t;
} v[2*N];
inline bool cmp(S a, S b)
{
if(a.f != b.f) return a.f > b.f;
return a.t < b.t;
}
int n, m, soma;
ll dp[2][50*N];
ll solve()
{
ll A = (n + m + 1)%2, B = (n + m)%2;
for(int i = n + m + 1; i >= 1; i--)
{
for(int C = 0; C <= soma; C++)
{
if(i > n + m) dp[A][C] = 0;
else
{
if(v[i].t == 0)
{
ll buy = dp[B][C + v[i].c] - (ll)v[i].val;
ll nop = dp[B][C];
dp[A][C] = max(buy, nop);
}
else
{
ll get = ( v[i].c <= C ? dp[B][C - v[i].c] + (ll)v[i].val : 0);
ll nop = dp[B][C];
dp[A][C] = max(nop, get);
}
}
}
swap(A, B);
}
return dp[1][0];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i = 1; i <= n; i++) cin>>v[i].c>>v[i].f>>v[i].val, v[i].t = 0, soma += v[i].c;
cin>>m;
for(int i = n + 1; i <= n + m; i++) cin>>v[i].c>>v[i].f>>v[i].val, v[i].t = 1;
sort(v + 1, v + n + m + 1, cmp);
cout<<solve()<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
5 ms |
560 KB |
Output is correct |
6 |
Correct |
4 ms |
560 KB |
Output is correct |
7 |
Correct |
8 ms |
560 KB |
Output is correct |
8 |
Correct |
7 ms |
560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
560 KB |
Output is correct |
2 |
Correct |
2 ms |
560 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
53 ms |
980 KB |
Output is correct |
6 |
Correct |
4 ms |
980 KB |
Output is correct |
7 |
Correct |
232 ms |
1464 KB |
Output is correct |
8 |
Correct |
48 ms |
1464 KB |
Output is correct |
9 |
Correct |
375 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Correct |
2 ms |
2132 KB |
Output is correct |
3 |
Correct |
3 ms |
2132 KB |
Output is correct |
4 |
Correct |
3 ms |
2132 KB |
Output is correct |
5 |
Correct |
3 ms |
2132 KB |
Output is correct |
6 |
Correct |
3 ms |
2132 KB |
Output is correct |
7 |
Correct |
3 ms |
2132 KB |
Output is correct |
8 |
Correct |
3 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2132 KB |
Output is correct |
2 |
Correct |
2 ms |
2132 KB |
Output is correct |
3 |
Correct |
17 ms |
2132 KB |
Output is correct |
4 |
Correct |
5 ms |
2132 KB |
Output is correct |
5 |
Correct |
445 ms |
2132 KB |
Output is correct |
6 |
Correct |
905 ms |
2132 KB |
Output is correct |
7 |
Correct |
893 ms |
2132 KB |
Output is correct |
8 |
Correct |
759 ms |
2172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2172 KB |
Output is correct |
2 |
Correct |
3 ms |
2172 KB |
Output is correct |
3 |
Correct |
48 ms |
2172 KB |
Output is correct |
4 |
Correct |
11 ms |
2172 KB |
Output is correct |
5 |
Correct |
868 ms |
2172 KB |
Output is correct |
6 |
Correct |
797 ms |
2176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
3 ms |
356 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
5 ms |
560 KB |
Output is correct |
6 |
Correct |
4 ms |
560 KB |
Output is correct |
7 |
Correct |
8 ms |
560 KB |
Output is correct |
8 |
Correct |
7 ms |
560 KB |
Output is correct |
9 |
Correct |
3 ms |
560 KB |
Output is correct |
10 |
Correct |
2 ms |
560 KB |
Output is correct |
11 |
Correct |
3 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
53 ms |
980 KB |
Output is correct |
14 |
Correct |
4 ms |
980 KB |
Output is correct |
15 |
Correct |
232 ms |
1464 KB |
Output is correct |
16 |
Correct |
48 ms |
1464 KB |
Output is correct |
17 |
Correct |
375 ms |
2132 KB |
Output is correct |
18 |
Correct |
2 ms |
2132 KB |
Output is correct |
19 |
Correct |
2 ms |
2132 KB |
Output is correct |
20 |
Correct |
3 ms |
2132 KB |
Output is correct |
21 |
Correct |
3 ms |
2132 KB |
Output is correct |
22 |
Correct |
3 ms |
2132 KB |
Output is correct |
23 |
Correct |
3 ms |
2132 KB |
Output is correct |
24 |
Correct |
3 ms |
2132 KB |
Output is correct |
25 |
Correct |
3 ms |
2132 KB |
Output is correct |
26 |
Correct |
2 ms |
2132 KB |
Output is correct |
27 |
Correct |
2 ms |
2132 KB |
Output is correct |
28 |
Correct |
17 ms |
2132 KB |
Output is correct |
29 |
Correct |
5 ms |
2132 KB |
Output is correct |
30 |
Correct |
445 ms |
2132 KB |
Output is correct |
31 |
Correct |
905 ms |
2132 KB |
Output is correct |
32 |
Correct |
893 ms |
2132 KB |
Output is correct |
33 |
Correct |
759 ms |
2172 KB |
Output is correct |
34 |
Correct |
2 ms |
2172 KB |
Output is correct |
35 |
Correct |
3 ms |
2172 KB |
Output is correct |
36 |
Correct |
48 ms |
2172 KB |
Output is correct |
37 |
Correct |
11 ms |
2172 KB |
Output is correct |
38 |
Correct |
868 ms |
2172 KB |
Output is correct |
39 |
Correct |
797 ms |
2176 KB |
Output is correct |
40 |
Correct |
54 ms |
2176 KB |
Output is correct |
41 |
Correct |
153 ms |
2176 KB |
Output is correct |
42 |
Correct |
16 ms |
2176 KB |
Output is correct |
43 |
Correct |
988 ms |
2332 KB |
Output is correct |
44 |
Correct |
932 ms |
2332 KB |
Output is correct |
45 |
Correct |
963 ms |
2332 KB |
Output is correct |
46 |
Correct |
7 ms |
2332 KB |
Output is correct |
47 |
Correct |
13 ms |
2332 KB |
Output is correct |
48 |
Correct |
14 ms |
2332 KB |
Output is correct |