// author : sentheta aka vanwij
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#define DBG 1
#else
#include"bits/stdc++.h"
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
Int ret = 1;
for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}
void solve(); int TC, ALLTC;
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
solve();
}
const int INF = 1e18;
const int N = 2005;
const int C = 52;
int n, m;
V<array<int,3>> ev;
// dp[x] = max profit if there is x cores to be fulfilled
int dp[N*C];
void solve(){
cin >> n;
rep(i,1,n+1){
int cnt, freq, price;
cin >> cnt >> freq >> price;
ev.push_back({freq,cnt,-price});
}
cin >> m;
rep(i,1,m+1){
int cnt, freq, price;
cin >> cnt >> freq >> price;
ev.push_back({freq,-cnt,price});
}
sort(all(ev));
dp[0] = 0;
rep(i,1,N*C) dp[i] = -INF;
int tot = 0;
for(auto[freq,cnt,price] : ev){
dbg(freq); dbg(cnt); dbg(price);
// computers
if(cnt > 0){
cerr << "COMPUTER" << nl;
cnt = abs(cnt); price = abs(price);
rep(i,0,tot+1){
int j = max(0LL, i-cnt);
dp[j] = max(dp[j], dp[i]-price);
}
}
// orders
else{
cerr << "ORDER" << nl;
cnt = abs(cnt); price = abs(price);
for(int i=tot; i>=0; i--){
int j = i+cnt;
dp[j] = max(dp[j], dp[i]+price);
}
tot += cnt;
}
cerr << nl;
}
int ans = dp[0];
cout << ans << nl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1104 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 |
37 ms |
1256 KB |
Output is correct |
6 |
Correct |
17 ms |
1244 KB |
Output is correct |
7 |
Correct |
71 ms |
1236 KB |
Output is correct |
8 |
Correct |
68 ms |
1236 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 |
1 ms |
1108 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
2 ms |
1236 KB |
Output is correct |
8 |
Correct |
2 ms |
1236 KB |
Output is correct |
9 |
Correct |
3 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1108 KB |
Output is correct |
2 |
Correct |
1 ms |
1104 KB |
Output is correct |
3 |
Correct |
1 ms |
1096 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
1 ms |
1104 KB |
Output is correct |
6 |
Correct |
1 ms |
1100 KB |
Output is correct |
7 |
Correct |
1 ms |
1108 KB |
Output is correct |
8 |
Correct |
1 ms |
1108 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 |
1236 KB |
Output is correct |
4 |
Correct |
9 ms |
1236 KB |
Output is correct |
5 |
Correct |
127 ms |
1376 KB |
Output is correct |
6 |
Correct |
255 ms |
1324 KB |
Output is correct |
7 |
Correct |
253 ms |
1364 KB |
Output is correct |
8 |
Correct |
235 ms |
1364 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 |
5 ms |
1248 KB |
Output is correct |
5 |
Correct |
152 ms |
1364 KB |
Output is correct |
6 |
Correct |
260 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1104 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 |
37 ms |
1256 KB |
Output is correct |
6 |
Correct |
17 ms |
1244 KB |
Output is correct |
7 |
Correct |
71 ms |
1236 KB |
Output is correct |
8 |
Correct |
68 ms |
1236 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 |
1 ms |
1108 KB |
Output is correct |
14 |
Correct |
1 ms |
1112 KB |
Output is correct |
15 |
Correct |
2 ms |
1236 KB |
Output is correct |
16 |
Correct |
2 ms |
1236 KB |
Output is correct |
17 |
Correct |
3 ms |
1236 KB |
Output is correct |
18 |
Correct |
1 ms |
1108 KB |
Output is correct |
19 |
Correct |
1 ms |
1104 KB |
Output is correct |
20 |
Correct |
1 ms |
1096 KB |
Output is correct |
21 |
Correct |
1 ms |
1108 KB |
Output is correct |
22 |
Correct |
1 ms |
1104 KB |
Output is correct |
23 |
Correct |
1 ms |
1100 KB |
Output is correct |
24 |
Correct |
1 ms |
1108 KB |
Output is correct |
25 |
Correct |
1 ms |
1108 KB |
Output is correct |
26 |
Correct |
1 ms |
1108 KB |
Output is correct |
27 |
Correct |
1 ms |
1108 KB |
Output is correct |
28 |
Correct |
1 ms |
1236 KB |
Output is correct |
29 |
Correct |
9 ms |
1236 KB |
Output is correct |
30 |
Correct |
127 ms |
1376 KB |
Output is correct |
31 |
Correct |
255 ms |
1324 KB |
Output is correct |
32 |
Correct |
253 ms |
1364 KB |
Output is correct |
33 |
Correct |
235 ms |
1364 KB |
Output is correct |
34 |
Correct |
1 ms |
1108 KB |
Output is correct |
35 |
Correct |
1 ms |
1108 KB |
Output is correct |
36 |
Correct |
1 ms |
1108 KB |
Output is correct |
37 |
Correct |
5 ms |
1248 KB |
Output is correct |
38 |
Correct |
152 ms |
1364 KB |
Output is correct |
39 |
Correct |
260 ms |
1236 KB |
Output is correct |
40 |
Correct |
11 ms |
1108 KB |
Output is correct |
41 |
Correct |
43 ms |
1236 KB |
Output is correct |
42 |
Correct |
5 ms |
1240 KB |
Output is correct |
43 |
Correct |
270 ms |
1364 KB |
Output is correct |
44 |
Correct |
267 ms |
1372 KB |
Output is correct |
45 |
Correct |
169 ms |
1404 KB |
Output is correct |
46 |
Correct |
2 ms |
1236 KB |
Output is correct |
47 |
Correct |
5 ms |
1236 KB |
Output is correct |
48 |
Correct |
3 ms |
1236 KB |
Output is correct |