#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a), _b =(b); i <= _b; i++)
#define FORD(i, a, b) for(int i = (a), _b =(b); i >= _b; i--)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> i) & 1)
#define popc(i) __builtin_popcountll(i)
#define fi first
#define se second
#define ALL(v) (v).begin(),(v).end()
#define pii pair<int, int>
using ll = long long;
using namespace std;
const int maxn = 2e3 + 10;
int n,m;
struct state{
int c,f,v;
bool operator < (const state &other) const{
return f > other.f;
}
};
vector<state> com;
vector<state> cus;
int maxcnt;
long long res(0);
namespace sub3{
const int maxn1 = 2e3 + 2;
long long dp[2][maxn1][101];
void solve(){
memset(dp,-0x3f,sizeof dp);
long long oo = dp[1][1][1];
dp[0][0][0] = 0;
FOR(i,0,n){
memset(dp[(i + 1) & 1],-0x3f,sizeof dp[(i + 1) & 1]);
FOR(j,0,m)
FOR(cnt,0,100)
if(dp[i & 1][j][cnt] > oo){
if(i < n)
dp[(i + 1) & 1][j][cnt] = max(dp[(i + 1) & 1][j][cnt],dp[i & 1][j][cnt]);
if(j < m)
dp[i & 1][j + 1][cnt] = max(dp[i & 1][j + 1][cnt],dp[i & 1][j][cnt]);
if(i < n && cnt + com[i + 1].c <= 100)
dp[(i + 1) & 1][j][cnt + com[i + 1].c] = max(dp[(i + 1) & 1][j][cnt + com[i + 1].c],dp[i & 1][j][cnt] - com[i + 1].v);
if(i >= 1 && cnt >= cus[j + 1].c && com[i].f >= cus[j + 1].f && j < m)
dp[i & 1][j + 1][cnt - cus[j + 1].c] = max(dp[i & 1][j + 1][cnt - cus[j + 1].c],dp[i & 1][j][cnt] + cus[j + 1].v);
}
}
FOR(cnt,0,100)
res = max(res,dp[n & 1][m][cnt]);
cout << res;
}
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
#define task "test"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n;
FOR(i,1,n){
int c,f,v;
cin >> c >> f >> v;
com.push_back({c,f,v});
}
int tmp = 1e9;
com.push_back({0,tmp + 1,-1});
sort(ALL(com));
cin >> m;
FOR(i,1,m){
int c,f,v;
cin >> c >> f >> v;
cus.push_back({c,f,v});
}
cus.push_back({0,tmp + 1,-1});
sort(ALL(cus));
sub3::solve();
}
Compilation message
clo.cpp: In function 'int main()':
clo.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
clo.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3416 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
13 ms |
3676 KB |
Output is correct |
6 |
Correct |
4 ms |
3420 KB |
Output is correct |
7 |
Correct |
8 ms |
3420 KB |
Output is correct |
8 |
Correct |
11 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3416 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
4 ms |
3420 KB |
Output is correct |
4 |
Correct |
4 ms |
3420 KB |
Output is correct |
5 |
Correct |
31 ms |
3416 KB |
Output is correct |
6 |
Correct |
28 ms |
3416 KB |
Output is correct |
7 |
Correct |
61 ms |
3416 KB |
Output is correct |
8 |
Correct |
66 ms |
3420 KB |
Output is correct |
9 |
Correct |
61 ms |
3416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
5 ms |
3624 KB |
Output is correct |
4 |
Correct |
7 ms |
3420 KB |
Output is correct |
5 |
Correct |
20 ms |
3416 KB |
Output is correct |
6 |
Correct |
21 ms |
3420 KB |
Output is correct |
7 |
Correct |
32 ms |
3612 KB |
Output is correct |
8 |
Correct |
35 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3676 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
42 ms |
3420 KB |
Output is correct |
4 |
Correct |
11 ms |
3676 KB |
Output is correct |
5 |
Correct |
1622 ms |
3924 KB |
Output is correct |
6 |
Correct |
1633 ms |
3676 KB |
Output is correct |
7 |
Correct |
1681 ms |
3672 KB |
Output is correct |
8 |
Correct |
1597 ms |
3676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3420 KB |
Output is correct |
2 |
Correct |
4 ms |
3420 KB |
Output is correct |
3 |
Correct |
73 ms |
3620 KB |
Output is correct |
4 |
Correct |
538 ms |
3676 KB |
Output is correct |
5 |
Correct |
1496 ms |
3672 KB |
Output is correct |
6 |
Correct |
1643 ms |
3672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
3416 KB |
Output is correct |
2 |
Correct |
1 ms |
3420 KB |
Output is correct |
3 |
Correct |
1 ms |
3420 KB |
Output is correct |
4 |
Correct |
1 ms |
3420 KB |
Output is correct |
5 |
Correct |
13 ms |
3676 KB |
Output is correct |
6 |
Correct |
4 ms |
3420 KB |
Output is correct |
7 |
Correct |
8 ms |
3420 KB |
Output is correct |
8 |
Correct |
11 ms |
3420 KB |
Output is correct |
9 |
Correct |
2 ms |
3416 KB |
Output is correct |
10 |
Correct |
1 ms |
3420 KB |
Output is correct |
11 |
Correct |
4 ms |
3420 KB |
Output is correct |
12 |
Correct |
4 ms |
3420 KB |
Output is correct |
13 |
Correct |
31 ms |
3416 KB |
Output is correct |
14 |
Correct |
28 ms |
3416 KB |
Output is correct |
15 |
Correct |
61 ms |
3416 KB |
Output is correct |
16 |
Correct |
66 ms |
3420 KB |
Output is correct |
17 |
Correct |
61 ms |
3416 KB |
Output is correct |
18 |
Correct |
1 ms |
3420 KB |
Output is correct |
19 |
Correct |
1 ms |
3420 KB |
Output is correct |
20 |
Correct |
5 ms |
3624 KB |
Output is correct |
21 |
Correct |
7 ms |
3420 KB |
Output is correct |
22 |
Correct |
20 ms |
3416 KB |
Output is correct |
23 |
Correct |
21 ms |
3420 KB |
Output is correct |
24 |
Correct |
32 ms |
3612 KB |
Output is correct |
25 |
Correct |
35 ms |
3420 KB |
Output is correct |
26 |
Correct |
2 ms |
3676 KB |
Output is correct |
27 |
Correct |
1 ms |
3420 KB |
Output is correct |
28 |
Correct |
42 ms |
3420 KB |
Output is correct |
29 |
Correct |
11 ms |
3676 KB |
Output is correct |
30 |
Correct |
1622 ms |
3924 KB |
Output is correct |
31 |
Correct |
1633 ms |
3676 KB |
Output is correct |
32 |
Correct |
1681 ms |
3672 KB |
Output is correct |
33 |
Correct |
1597 ms |
3676 KB |
Output is correct |
34 |
Correct |
1 ms |
3420 KB |
Output is correct |
35 |
Correct |
4 ms |
3420 KB |
Output is correct |
36 |
Correct |
73 ms |
3620 KB |
Output is correct |
37 |
Correct |
538 ms |
3676 KB |
Output is correct |
38 |
Correct |
1496 ms |
3672 KB |
Output is correct |
39 |
Correct |
1643 ms |
3672 KB |
Output is correct |
40 |
Correct |
108 ms |
3416 KB |
Output is correct |
41 |
Correct |
371 ms |
3652 KB |
Output is correct |
42 |
Correct |
1178 ms |
3676 KB |
Output is correct |
43 |
Correct |
299 ms |
3672 KB |
Output is correct |
44 |
Correct |
299 ms |
3676 KB |
Output is correct |
45 |
Correct |
288 ms |
3676 KB |
Output is correct |
46 |
Correct |
517 ms |
3636 KB |
Output is correct |
47 |
Correct |
1142 ms |
3672 KB |
Output is correct |
48 |
Correct |
1064 ms |
3924 KB |
Output is correct |