#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=2007;
ll n,m,k;
struct Point{
bool is_order;
int f,c,v;
Point(int fff, int cc, int vv, bool b):f(fff),c(cc),v(vv),is_order(b){}
bool operator<(const Point& other)const{
if(f==other.f){
return is_order>other.is_order;
}
return f<other.f;
}
};
vector<Point>a;
ll dp[2][N*51];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin>>n;
for(int i=0;i<n;i++){
int c,f,v;
cin>>c>>f>>v;
a.push_back(Point(f,c,-v,false));
}
cin>>m;
for(int i=0;i<m;i++){
int c,f,v;
cin>>c>>f>>v;
a.push_back(Point(f,-c,v,true));
}
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
// for(int i=0;i<a.size();i++){
// cout<<i<<": "<<a[i].f<<" "<<a[i].c<<" "<<a[i].v<<endl;
// }
fill(dp[0],dp[0]+N*51-1,-INF);
dp[0][0]=0;
for(int i=0;i<a.size();i++){
for(int j=0;j<n*51;j++){
dp[1][j]=dp[0][j];
if(j-a[i].c>=0){
dp[1][j]=max(dp[1][j],dp[0][j-a[i].c]+a[i].v);
}
}
for(int j=0;j<n*51;j++){
dp[0][j]=dp[1][j];
// cout<<dp[0][j]<<" ";
}
// cout<<endl;
}
ll res=0;
for(int j=0;j<n*51;j++){
res=max(res,dp[0][j]);
}
cout<<res<<endl;
}
Compilation message
clo.cpp: In constructor 'Point::Point(int, int, int, bool)':
clo.cpp:19:13: warning: 'Point::v' will be initialized after [-Wreorder]
19 | int f,c,v;
| ^
clo.cpp:18:10: warning: 'bool Point::is_order' [-Wreorder]
18 | bool is_order;
| ^~~~~~~~
clo.cpp:20:5: warning: when initialized here [-Wreorder]
20 | Point(int fff, int cc, int vv, bool b):f(fff),c(cc),v(vv),is_order(b){}
| ^~~~~
clo.cpp: In function 'int main()':
clo.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1108 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
3 ms |
1236 KB |
Output is correct |
6 |
Correct |
3 ms |
1236 KB |
Output is correct |
7 |
Correct |
3 ms |
1236 KB |
Output is correct |
8 |
Correct |
3 ms |
1240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1108 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
60 ms |
1492 KB |
Output is correct |
6 |
Correct |
60 ms |
1492 KB |
Output is correct |
7 |
Correct |
295 ms |
2016 KB |
Output is correct |
8 |
Correct |
294 ms |
2016 KB |
Output is correct |
9 |
Correct |
277 ms |
2004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1096 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
2 ms |
1108 KB |
Output is correct |
4 |
Correct |
2 ms |
1108 KB |
Output is correct |
5 |
Correct |
6 ms |
1108 KB |
Output is correct |
6 |
Correct |
6 ms |
1240 KB |
Output is correct |
7 |
Correct |
10 ms |
1256 KB |
Output is correct |
8 |
Correct |
9 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1096 KB |
Output is correct |
2 |
Correct |
1 ms |
1100 KB |
Output is correct |
3 |
Correct |
180 ms |
1748 KB |
Output is correct |
4 |
Correct |
2 ms |
1108 KB |
Output is correct |
5 |
Correct |
554 ms |
2084 KB |
Output is correct |
6 |
Correct |
583 ms |
2084 KB |
Output is correct |
7 |
Correct |
576 ms |
2084 KB |
Output is correct |
8 |
Correct |
565 ms |
2056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
2 ms |
1108 KB |
Output is correct |
3 |
Correct |
33 ms |
1364 KB |
Output is correct |
4 |
Correct |
115 ms |
1504 KB |
Output is correct |
5 |
Correct |
566 ms |
2076 KB |
Output is correct |
6 |
Correct |
590 ms |
2068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
1108 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
3 ms |
1236 KB |
Output is correct |
6 |
Correct |
3 ms |
1236 KB |
Output is correct |
7 |
Correct |
3 ms |
1236 KB |
Output is correct |
8 |
Correct |
3 ms |
1240 KB |
Output is correct |
9 |
Correct |
1 ms |
1108 KB |
Output is correct |
10 |
Correct |
1 ms |
1108 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
1 ms |
1108 KB |
Output is correct |
13 |
Correct |
60 ms |
1492 KB |
Output is correct |
14 |
Correct |
60 ms |
1492 KB |
Output is correct |
15 |
Correct |
295 ms |
2016 KB |
Output is correct |
16 |
Correct |
294 ms |
2016 KB |
Output is correct |
17 |
Correct |
277 ms |
2004 KB |
Output is correct |
18 |
Correct |
1 ms |
1096 KB |
Output is correct |
19 |
Correct |
1 ms |
1108 KB |
Output is correct |
20 |
Correct |
2 ms |
1108 KB |
Output is correct |
21 |
Correct |
2 ms |
1108 KB |
Output is correct |
22 |
Correct |
6 ms |
1108 KB |
Output is correct |
23 |
Correct |
6 ms |
1240 KB |
Output is correct |
24 |
Correct |
10 ms |
1256 KB |
Output is correct |
25 |
Correct |
9 ms |
1236 KB |
Output is correct |
26 |
Correct |
1 ms |
1096 KB |
Output is correct |
27 |
Correct |
1 ms |
1100 KB |
Output is correct |
28 |
Correct |
180 ms |
1748 KB |
Output is correct |
29 |
Correct |
2 ms |
1108 KB |
Output is correct |
30 |
Correct |
554 ms |
2084 KB |
Output is correct |
31 |
Correct |
583 ms |
2084 KB |
Output is correct |
32 |
Correct |
576 ms |
2084 KB |
Output is correct |
33 |
Correct |
565 ms |
2056 KB |
Output is correct |
34 |
Correct |
1 ms |
1108 KB |
Output is correct |
35 |
Correct |
2 ms |
1108 KB |
Output is correct |
36 |
Correct |
33 ms |
1364 KB |
Output is correct |
37 |
Correct |
115 ms |
1504 KB |
Output is correct |
38 |
Correct |
566 ms |
2076 KB |
Output is correct |
39 |
Correct |
590 ms |
2068 KB |
Output is correct |
40 |
Correct |
37 ms |
1364 KB |
Output is correct |
41 |
Correct |
110 ms |
1504 KB |
Output is correct |
42 |
Correct |
334 ms |
1888 KB |
Output is correct |
43 |
Correct |
582 ms |
2084 KB |
Output is correct |
44 |
Correct |
570 ms |
2128 KB |
Output is correct |
45 |
Correct |
580 ms |
2132 KB |
Output is correct |
46 |
Correct |
147 ms |
1596 KB |
Output is correct |
47 |
Correct |
341 ms |
1876 KB |
Output is correct |
48 |
Correct |
339 ms |
1868 KB |
Output is correct |