#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Computer{
int c, f, v;
Computer (int _c=0, int _f=0, int _v=0): c(_c), f(_f), v(_v){}
bool operator<(const Computer &b){
return f<b.f;
}
};
const int N=2010, inf=1e18;
int f[N*50];
int n, m;
Computer a[N];
vector<pair<int, int>> vv[N];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i=1; i<=n; ++i) cin >> a[i].c >> a[i].f >> a[i].v;
sort(a+1, a+n+1);
cin >> m;
for (int i=1; i<=m; ++i){
Computer b;
cin >> b.c >> b.f >> b.v;
if (b.f>a[n].f) continue;
vv[lower_bound(a+1, a+n+1, b)-a].emplace_back(b.c, b.v);
}
for (int i=0; i<N*50; ++i) f[i]=-inf;
f[0]=0;
for (int i=n; i>=1; --i){
for (int j=(n-i)*50; j>=0; --j) f[j+a[i].c]=max(f[j+a[i].c], f[j]-a[i].v);
int mx=0;
for (int j=0; j<=(n-i+1)*50; ++j) if (f[j]!=-inf) mx=j;
for (auto &j:vv[i]){
int c=j.first, v=j.second;
for (int k=c; k<=mx; ++k) if (f[k]!=-inf) f[k-c]=max(f[k-c], f[k]+v);
}
}
cout << *max_element(f, f+N*50) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1648 KB |
Output is correct |
6 |
Correct |
1 ms |
1372 KB |
Output is correct |
7 |
Correct |
2 ms |
1440 KB |
Output is correct |
8 |
Correct |
2 ms |
1404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
25 ms |
1116 KB |
Output is correct |
6 |
Correct |
27 ms |
1112 KB |
Output is correct |
7 |
Correct |
123 ms |
1372 KB |
Output is correct |
8 |
Correct |
115 ms |
1372 KB |
Output is correct |
9 |
Correct |
110 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
2 ms |
1116 KB |
Output is correct |
6 |
Correct |
3 ms |
1328 KB |
Output is correct |
7 |
Correct |
3 ms |
1112 KB |
Output is correct |
8 |
Correct |
5 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1116 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
67 ms |
1328 KB |
Output is correct |
4 |
Correct |
2 ms |
1368 KB |
Output is correct |
5 |
Correct |
189 ms |
1372 KB |
Output is correct |
6 |
Correct |
269 ms |
1616 KB |
Output is correct |
7 |
Correct |
261 ms |
1428 KB |
Output is correct |
8 |
Correct |
248 ms |
1420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1120 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
13 ms |
1116 KB |
Output is correct |
4 |
Correct |
23 ms |
1420 KB |
Output is correct |
5 |
Correct |
186 ms |
1372 KB |
Output is correct |
6 |
Correct |
264 ms |
1404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1116 KB |
Output is correct |
3 |
Correct |
1 ms |
1116 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
1 ms |
1648 KB |
Output is correct |
6 |
Correct |
1 ms |
1372 KB |
Output is correct |
7 |
Correct |
2 ms |
1440 KB |
Output is correct |
8 |
Correct |
2 ms |
1404 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
1 ms |
1116 KB |
Output is correct |
11 |
Correct |
1 ms |
1116 KB |
Output is correct |
12 |
Correct |
1 ms |
1116 KB |
Output is correct |
13 |
Correct |
25 ms |
1116 KB |
Output is correct |
14 |
Correct |
27 ms |
1112 KB |
Output is correct |
15 |
Correct |
123 ms |
1372 KB |
Output is correct |
16 |
Correct |
115 ms |
1372 KB |
Output is correct |
17 |
Correct |
110 ms |
1368 KB |
Output is correct |
18 |
Correct |
1 ms |
1116 KB |
Output is correct |
19 |
Correct |
1 ms |
1116 KB |
Output is correct |
20 |
Correct |
1 ms |
1116 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
2 ms |
1116 KB |
Output is correct |
23 |
Correct |
3 ms |
1328 KB |
Output is correct |
24 |
Correct |
3 ms |
1112 KB |
Output is correct |
25 |
Correct |
5 ms |
1116 KB |
Output is correct |
26 |
Correct |
1 ms |
1116 KB |
Output is correct |
27 |
Correct |
1 ms |
1116 KB |
Output is correct |
28 |
Correct |
67 ms |
1328 KB |
Output is correct |
29 |
Correct |
2 ms |
1368 KB |
Output is correct |
30 |
Correct |
189 ms |
1372 KB |
Output is correct |
31 |
Correct |
269 ms |
1616 KB |
Output is correct |
32 |
Correct |
261 ms |
1428 KB |
Output is correct |
33 |
Correct |
248 ms |
1420 KB |
Output is correct |
34 |
Correct |
1 ms |
1120 KB |
Output is correct |
35 |
Correct |
1 ms |
1116 KB |
Output is correct |
36 |
Correct |
13 ms |
1116 KB |
Output is correct |
37 |
Correct |
23 ms |
1420 KB |
Output is correct |
38 |
Correct |
186 ms |
1372 KB |
Output is correct |
39 |
Correct |
264 ms |
1404 KB |
Output is correct |
40 |
Correct |
13 ms |
1116 KB |
Output is correct |
41 |
Correct |
35 ms |
1372 KB |
Output is correct |
42 |
Correct |
70 ms |
1372 KB |
Output is correct |
43 |
Correct |
293 ms |
1444 KB |
Output is correct |
44 |
Correct |
292 ms |
1440 KB |
Output is correct |
45 |
Correct |
195 ms |
1372 KB |
Output is correct |
46 |
Correct |
30 ms |
1372 KB |
Output is correct |
47 |
Correct |
71 ms |
1372 KB |
Output is correct |
48 |
Correct |
67 ms |
1368 KB |
Output is correct |