#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2004;
typedef long long ll;
const ll inf = 1e18;
struct ev
{
int c, v, f, tip;
} a[2 * Nmax];
int n, m;
void solve()
{
vector<ll> dp(50 * (n - m) + 1), old(50 * (n - m) + 1, -inf);
int i, j;
old[0] = 0;
for(i=1; i<=n; ++i)
{
if(a[i].tip == 0)
{
for(j=0; j<a[i].c; ++j) dp[j] = old[j];
for(j=a[i].c; j<dp.size(); ++j)
dp[j] = max(old[j], old[j-a[i].c] - a[i].v);
}
else
{
for(j=0; j + a[i].c < dp.size(); ++j)
dp[j] = max(old[j], old[j+a[i].c] + a[i].v);
for(; j < dp.size(); ++j)
dp[j] = old[j];
}
swap(dp, old);
}
cout << ( *max_element(old.begin(), old.end()) ) << '\n';
}
int main()
{
// freopen("input", "r", stdin);
cin.tie(0); cin.sync_with_stdio(false);
int i, C, F, V;
cin >> n;
for(i=1; i<=n; ++i)
{
cin >> C >> F >> V;
a[i] = {C, V, F, 0};
}
cin >> m;
for(i=1; i<=m; ++i)
{
cin >> C >> F >> V;
a[i+n] = {C, V, F, 1};
}
n += m;
sort(a+1, a+n+1, [] (ev x, ev y)
{
if(x.f != y.f) return x.f > y.f;
return x.tip < y.tip;
}
);
solve();
return 0;
}
Compilation message
clo.cpp: In function 'void solve()':
clo.cpp:29:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=a[i].c; j<dp.size(); ++j)
~^~~~~~~~~~
clo.cpp:34:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j + a[i].c < dp.size(); ++j)
~~~~~~~~~~~^~~~~~~~~~~
clo.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j < dp.size(); ++j)
~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
352 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
49 ms |
1144 KB |
Output is correct |
6 |
Correct |
58 ms |
1164 KB |
Output is correct |
7 |
Correct |
226 ms |
2040 KB |
Output is correct |
8 |
Correct |
272 ms |
2140 KB |
Output is correct |
9 |
Correct |
219 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
504 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
9 ms |
504 KB |
Output is correct |
8 |
Correct |
8 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
152 ms |
1604 KB |
Output is correct |
4 |
Correct |
4 ms |
376 KB |
Output is correct |
5 |
Correct |
405 ms |
2044 KB |
Output is correct |
6 |
Correct |
432 ms |
2168 KB |
Output is correct |
7 |
Correct |
425 ms |
2076 KB |
Output is correct |
8 |
Correct |
407 ms |
2140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
508 KB |
Output is correct |
3 |
Correct |
27 ms |
888 KB |
Output is correct |
4 |
Correct |
96 ms |
1120 KB |
Output is correct |
5 |
Correct |
410 ms |
2068 KB |
Output is correct |
6 |
Correct |
418 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
352 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
49 ms |
1144 KB |
Output is correct |
14 |
Correct |
58 ms |
1164 KB |
Output is correct |
15 |
Correct |
226 ms |
2040 KB |
Output is correct |
16 |
Correct |
272 ms |
2140 KB |
Output is correct |
17 |
Correct |
219 ms |
2040 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
6 ms |
504 KB |
Output is correct |
23 |
Correct |
7 ms |
504 KB |
Output is correct |
24 |
Correct |
9 ms |
504 KB |
Output is correct |
25 |
Correct |
8 ms |
632 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
152 ms |
1604 KB |
Output is correct |
29 |
Correct |
4 ms |
376 KB |
Output is correct |
30 |
Correct |
405 ms |
2044 KB |
Output is correct |
31 |
Correct |
432 ms |
2168 KB |
Output is correct |
32 |
Correct |
425 ms |
2076 KB |
Output is correct |
33 |
Correct |
407 ms |
2140 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
508 KB |
Output is correct |
36 |
Correct |
27 ms |
888 KB |
Output is correct |
37 |
Correct |
96 ms |
1120 KB |
Output is correct |
38 |
Correct |
410 ms |
2068 KB |
Output is correct |
39 |
Correct |
418 ms |
2040 KB |
Output is correct |
40 |
Correct |
31 ms |
860 KB |
Output is correct |
41 |
Correct |
79 ms |
1040 KB |
Output is correct |
42 |
Correct |
284 ms |
1672 KB |
Output is correct |
43 |
Correct |
433 ms |
2072 KB |
Output is correct |
44 |
Correct |
441 ms |
2168 KB |
Output is correct |
45 |
Correct |
426 ms |
2148 KB |
Output is correct |
46 |
Correct |
134 ms |
1272 KB |
Output is correct |
47 |
Correct |
275 ms |
1704 KB |
Output is correct |
48 |
Correct |
274 ms |
1656 KB |
Output is correct |