#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
#define ll long long
#define ld long double
const int MX = 100005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
char c = gc(); bool neg = false;
for(; c < '0'||'9' < c; c = gc())
if(c == '-') neg=true;
x = c - '0'; c = gc();
for(; '0' <= c && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c - '0');
if(neg) x = -x;
}
int n, m;
pair<int, pair<int, int> > a[MX];
ll dp[2][MX];
int main(){
cin(n);
for(int i = 1; i <= n; i ++){
cin(a[i].second.first); cin(a[i].first); cin(a[i].second.second);
a[i].second.second *= -1;
}
cin(m);
for(int i = n + 1; i <= n + m; i ++){
cin(a[i].second.first); cin(a[i].first); cin(a[i].second.second);
a[i].second.first *= -1;
}
sort(a + 1, a + n + m + 1, [&](pair<int, pair<int, int> > x, pair<int, pair<int, int> > y){
if(x.first == y.first) return x.second.first > y.second.first;
return x.first > y.first;
});
for(int i = 0; i < MX; i ++) dp[0][i] = -mod * 1ll * mod;
dp[0][0] = 0;
for(int i = 1; i <= n + m; i ++){
int nw = i % 2, bf = 1 - nw;
for(int j = 0; j < MX; j ++){
dp[nw][j] = dp[bf][j];
if(0 <= j - a[i].second.first && j - a[i].second.first < MX)
dp[nw][j] = max(dp[nw][j], dp[bf][j - a[i].second.first] + a[i].second.second);
}
}
ll ans = -mod * 1ll * mod;
for(int j = 0; j < MX; j ++)
ans = max(ans, dp[(n + m) % 2][j]);
printf("%lld\n", ans);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1900 KB |
Output is correct |
2 |
Correct |
2 ms |
1900 KB |
Output is correct |
3 |
Correct |
19 ms |
1900 KB |
Output is correct |
4 |
Correct |
35 ms |
1900 KB |
Output is correct |
5 |
Correct |
317 ms |
1900 KB |
Output is correct |
6 |
Correct |
313 ms |
1948 KB |
Output is correct |
7 |
Correct |
329 ms |
1948 KB |
Output is correct |
8 |
Correct |
331 ms |
1900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1900 KB |
Output is correct |
2 |
Correct |
3 ms |
1900 KB |
Output is correct |
3 |
Correct |
19 ms |
2028 KB |
Output is correct |
4 |
Correct |
19 ms |
1900 KB |
Output is correct |
5 |
Correct |
154 ms |
2028 KB |
Output is correct |
6 |
Correct |
150 ms |
1900 KB |
Output is correct |
7 |
Correct |
332 ms |
1948 KB |
Output is correct |
8 |
Correct |
330 ms |
1900 KB |
Output is correct |
9 |
Correct |
327 ms |
2028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1900 KB |
Output is correct |
2 |
Correct |
7 ms |
1900 KB |
Output is correct |
3 |
Correct |
31 ms |
2028 KB |
Output is correct |
4 |
Correct |
31 ms |
1900 KB |
Output is correct |
5 |
Correct |
60 ms |
1900 KB |
Output is correct |
6 |
Correct |
61 ms |
1900 KB |
Output is correct |
7 |
Correct |
86 ms |
1900 KB |
Output is correct |
8 |
Correct |
83 ms |
1900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
1900 KB |
Output is correct |
2 |
Correct |
5 ms |
1900 KB |
Output is correct |
3 |
Correct |
251 ms |
2028 KB |
Output is correct |
4 |
Correct |
324 ms |
1900 KB |
Output is correct |
5 |
Correct |
614 ms |
2024 KB |
Output is correct |
6 |
Correct |
651 ms |
2028 KB |
Output is correct |
7 |
Correct |
644 ms |
2028 KB |
Output is correct |
8 |
Correct |
631 ms |
2028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1900 KB |
Output is correct |
2 |
Correct |
28 ms |
1900 KB |
Output is correct |
3 |
Correct |
143 ms |
1900 KB |
Output is correct |
4 |
Correct |
330 ms |
2028 KB |
Output is correct |
5 |
Correct |
639 ms |
2028 KB |
Output is correct |
6 |
Correct |
650 ms |
2028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
1900 KB |
Output is correct |
2 |
Correct |
2 ms |
1900 KB |
Output is correct |
3 |
Correct |
19 ms |
1900 KB |
Output is correct |
4 |
Correct |
35 ms |
1900 KB |
Output is correct |
5 |
Correct |
317 ms |
1900 KB |
Output is correct |
6 |
Correct |
313 ms |
1948 KB |
Output is correct |
7 |
Correct |
329 ms |
1948 KB |
Output is correct |
8 |
Correct |
331 ms |
1900 KB |
Output is correct |
9 |
Correct |
3 ms |
1900 KB |
Output is correct |
10 |
Correct |
3 ms |
1900 KB |
Output is correct |
11 |
Correct |
19 ms |
2028 KB |
Output is correct |
12 |
Correct |
19 ms |
1900 KB |
Output is correct |
13 |
Correct |
154 ms |
2028 KB |
Output is correct |
14 |
Correct |
150 ms |
1900 KB |
Output is correct |
15 |
Correct |
332 ms |
1948 KB |
Output is correct |
16 |
Correct |
330 ms |
1900 KB |
Output is correct |
17 |
Correct |
327 ms |
2028 KB |
Output is correct |
18 |
Correct |
7 ms |
1900 KB |
Output is correct |
19 |
Correct |
7 ms |
1900 KB |
Output is correct |
20 |
Correct |
31 ms |
2028 KB |
Output is correct |
21 |
Correct |
31 ms |
1900 KB |
Output is correct |
22 |
Correct |
60 ms |
1900 KB |
Output is correct |
23 |
Correct |
61 ms |
1900 KB |
Output is correct |
24 |
Correct |
86 ms |
1900 KB |
Output is correct |
25 |
Correct |
83 ms |
1900 KB |
Output is correct |
26 |
Correct |
5 ms |
1900 KB |
Output is correct |
27 |
Correct |
5 ms |
1900 KB |
Output is correct |
28 |
Correct |
251 ms |
2028 KB |
Output is correct |
29 |
Correct |
324 ms |
1900 KB |
Output is correct |
30 |
Correct |
614 ms |
2024 KB |
Output is correct |
31 |
Correct |
651 ms |
2028 KB |
Output is correct |
32 |
Correct |
644 ms |
2028 KB |
Output is correct |
33 |
Correct |
631 ms |
2028 KB |
Output is correct |
34 |
Correct |
3 ms |
1900 KB |
Output is correct |
35 |
Correct |
28 ms |
1900 KB |
Output is correct |
36 |
Correct |
143 ms |
1900 KB |
Output is correct |
37 |
Correct |
330 ms |
2028 KB |
Output is correct |
38 |
Correct |
639 ms |
2028 KB |
Output is correct |
39 |
Correct |
650 ms |
2028 KB |
Output is correct |
40 |
Correct |
168 ms |
1900 KB |
Output is correct |
41 |
Correct |
313 ms |
2028 KB |
Output is correct |
42 |
Correct |
490 ms |
2000 KB |
Output is correct |
43 |
Correct |
645 ms |
2028 KB |
Output is correct |
44 |
Correct |
650 ms |
2156 KB |
Output is correct |
45 |
Correct |
647 ms |
2064 KB |
Output is correct |
46 |
Correct |
325 ms |
2028 KB |
Output is correct |
47 |
Correct |
490 ms |
2028 KB |
Output is correct |
48 |
Correct |
493 ms |
2028 KB |
Output is correct |