#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
using namespace std;
const int MAXN = 2005;
const int MAXCOL = 101;
const long long INF = 1e18;
typedef long long ll;
int n, m;
vector<pair<int, pair<int, int>>> comp;
vector<pair<int, pair<int, int>>> cust;
ll dp[MAXCOL][MAXN];
int ind = 0;
void get_index(int f) {
while(ind < n && comp[ind].first >= f) ++ind;
}
void fill() {
for (int i = 0; i < MAXCOL; ++i) for (int j = 0; j < MAXN; j++) dp[i][j] = -INF;
}
void outdp() {
for (int i = 0; i <= n; i++) {
for (int col = 0; col <= 30; ++col) {
cout << "i: " << i << ' ' << col << ' ' << dp[i][col] << endl;
}
}
}
void solve() {
fill();
for (int j = 0; j < n; j++) dp[0][j] = 0;
for (int i = 0; i < m; i++) {
int curf = cust[i].first, curc = cust[i].second.first, curv = cust[i].second.second;
get_index(curf);
for (int j = 0; j <= n; j++) {
for (int col = 0; col < MAXCOL; ++col) {
if (dp[col][j] == -INF) continue;
if (j < ind) {
if (col + comp[j].second.first < MAXCOL) {
dp[col + comp[j].second.first][j + 1] = max(dp[col + comp[j].second.first][j + 1],
dp[col][j] - comp[j].second.second);
}
}
if (j != n) dp[col][j + 1] = max(dp[col][j + 1], dp[col][j]);
if (curc <= col) {
dp[col - curc][j] = max(dp[col - curc][j],
dp[col][j] + curv);
}
}
}
}
ll ans = 0;
for (int i = 0; i <= n; i++) {
for (int j = 0; j < MAXCOL; j++) {
ans = max(ans, dp[j][i]);
}
}
cout << ans << endl;
}
void outvector(vector<pair<int, pair<int, int>>>& a) {
int sz = a.size();
for (int i = 0; i < sz; ++i) {
cout << "i: " << i << endl;
cout << a[i].first << ' ' << a[i].second.first << ' ' << a[i].second.second << endl;
}
}
int main() {
//freopen("test.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
comp.resize(n);
for (int i = 0; i < n; i++) {
int c, f, v;
cin >> c >> f >> v;
comp[i] = {f, {c, v}};
}
cin >> m;
cust.resize(m);
for (int i = 0; i < m; i++) {
int c, f, v;
cin >> c >> f >> v;
cust[i] = {f, {c, v}};
}
sort(comp.begin(), comp.end());
reverse(comp.begin(), comp.end());
sort(cust.begin(), cust.end());
reverse(cust.begin(), cust.end());
//cout << "comp: " << endl;
//// outvector(comp);
// cout << "cust: " << endl;
//outvector(cust);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
4 ms |
1916 KB |
Output is correct |
4 |
Correct |
4 ms |
1912 KB |
Output is correct |
5 |
Correct |
15 ms |
1912 KB |
Output is correct |
6 |
Correct |
8 ms |
2040 KB |
Output is correct |
7 |
Correct |
12 ms |
1912 KB |
Output is correct |
8 |
Correct |
14 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
4 ms |
1912 KB |
Output is correct |
4 |
Correct |
4 ms |
1916 KB |
Output is correct |
5 |
Correct |
10 ms |
1912 KB |
Output is correct |
6 |
Correct |
10 ms |
1912 KB |
Output is correct |
7 |
Correct |
19 ms |
2040 KB |
Output is correct |
8 |
Correct |
25 ms |
1912 KB |
Output is correct |
9 |
Correct |
16 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
4 ms |
1912 KB |
Output is correct |
4 |
Correct |
4 ms |
1912 KB |
Output is correct |
5 |
Correct |
22 ms |
1976 KB |
Output is correct |
6 |
Correct |
22 ms |
2040 KB |
Output is correct |
7 |
Correct |
27 ms |
1912 KB |
Output is correct |
8 |
Correct |
29 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
11 ms |
2024 KB |
Output is correct |
4 |
Correct |
17 ms |
2040 KB |
Output is correct |
5 |
Correct |
2295 ms |
2064 KB |
Output is correct |
6 |
Correct |
2182 ms |
2040 KB |
Output is correct |
7 |
Correct |
2183 ms |
2060 KB |
Output is correct |
8 |
Correct |
2101 ms |
2068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
4 ms |
1912 KB |
Output is correct |
3 |
Correct |
75 ms |
2016 KB |
Output is correct |
4 |
Correct |
714 ms |
2008 KB |
Output is correct |
5 |
Correct |
1781 ms |
2072 KB |
Output is correct |
6 |
Correct |
2174 ms |
2036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1912 KB |
Output is correct |
2 |
Correct |
3 ms |
1912 KB |
Output is correct |
3 |
Correct |
4 ms |
1916 KB |
Output is correct |
4 |
Correct |
4 ms |
1912 KB |
Output is correct |
5 |
Correct |
15 ms |
1912 KB |
Output is correct |
6 |
Correct |
8 ms |
2040 KB |
Output is correct |
7 |
Correct |
12 ms |
1912 KB |
Output is correct |
8 |
Correct |
14 ms |
2040 KB |
Output is correct |
9 |
Correct |
3 ms |
1912 KB |
Output is correct |
10 |
Correct |
3 ms |
1912 KB |
Output is correct |
11 |
Correct |
4 ms |
1912 KB |
Output is correct |
12 |
Correct |
4 ms |
1916 KB |
Output is correct |
13 |
Correct |
10 ms |
1912 KB |
Output is correct |
14 |
Correct |
10 ms |
1912 KB |
Output is correct |
15 |
Correct |
19 ms |
2040 KB |
Output is correct |
16 |
Correct |
25 ms |
1912 KB |
Output is correct |
17 |
Correct |
16 ms |
1912 KB |
Output is correct |
18 |
Correct |
3 ms |
1912 KB |
Output is correct |
19 |
Correct |
3 ms |
1912 KB |
Output is correct |
20 |
Correct |
4 ms |
1912 KB |
Output is correct |
21 |
Correct |
4 ms |
1912 KB |
Output is correct |
22 |
Correct |
22 ms |
1976 KB |
Output is correct |
23 |
Correct |
22 ms |
2040 KB |
Output is correct |
24 |
Correct |
27 ms |
1912 KB |
Output is correct |
25 |
Correct |
29 ms |
1912 KB |
Output is correct |
26 |
Correct |
3 ms |
1912 KB |
Output is correct |
27 |
Correct |
3 ms |
1912 KB |
Output is correct |
28 |
Correct |
11 ms |
2024 KB |
Output is correct |
29 |
Correct |
17 ms |
2040 KB |
Output is correct |
30 |
Correct |
2295 ms |
2064 KB |
Output is correct |
31 |
Correct |
2182 ms |
2040 KB |
Output is correct |
32 |
Correct |
2183 ms |
2060 KB |
Output is correct |
33 |
Correct |
2101 ms |
2068 KB |
Output is correct |
34 |
Correct |
3 ms |
1912 KB |
Output is correct |
35 |
Correct |
4 ms |
1912 KB |
Output is correct |
36 |
Correct |
75 ms |
2016 KB |
Output is correct |
37 |
Correct |
714 ms |
2008 KB |
Output is correct |
38 |
Correct |
1781 ms |
2072 KB |
Output is correct |
39 |
Correct |
2174 ms |
2036 KB |
Output is correct |
40 |
Correct |
119 ms |
1988 KB |
Output is correct |
41 |
Correct |
401 ms |
2012 KB |
Output is correct |
42 |
Correct |
1318 ms |
2040 KB |
Output is correct |
43 |
Correct |
540 ms |
2168 KB |
Output is correct |
44 |
Correct |
533 ms |
2068 KB |
Output is correct |
45 |
Correct |
514 ms |
2040 KB |
Output is correct |
46 |
Correct |
556 ms |
2040 KB |
Output is correct |
47 |
Correct |
1251 ms |
2048 KB |
Output is correct |
48 |
Correct |
1226 ms |
2052 KB |
Output is correct |