#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#pragma GCC optimize("O3")
struct core {
int f, v;
};
struct comp {
int c, f, v;
};
bool cmp_comp(const comp &a, const comp &b)
{
return a.f < b.f;
}
const int N = 2010;
const int C = 52;
comp custs[N], comps[N];
ll dp[2][N][C*2];
int n, m;
void read_input()
{
cin >> n;
Loop (i,0,n) {
auto &[c, f, v] = comps[i];
cin >> c >> f >> v;
}
cin >> m;
Loop (i,0,m) {
auto &[c, f, v] = custs[i];
cin >> c >> f >> v;
}
sort(comps, comps+n, cmp_comp);
sort(custs, custs+m, cmp_comp);
}
template<class T>
void Smax(T &x, const T &y)
{
x = max(x, y);
}
void update_dp(int cus, int com, int used)
{
--cus; --com;
const int cus2 = cus&1;
Smax(dp[!cus2][com+1][used], dp[!cus2][com][min(C, used)]);
if (used >= C)
Smax(dp[!cus2][com+1][used], dp[cus2][com+1][used]);
if (comps[com].f < custs[cus].f)
return;
int remc_com = comps[com].c - max(0, used-C);
int remc_cus = custs[cus].c - max(0, C-used);
ll profit = (used >= C? custs[cus].v: 0)
- (used <= C? comps[com].v: 0);
if (remc_com > remc_cus) {
int new_used = C + (comps[com].c - (remc_com - remc_cus));
Smax(dp[!cus2][com+1][ used],
dp[ cus2][com+1][new_used] + profit);
} else if (remc_com < remc_cus) {
int new_used = C - (custs[cus].c - (remc_cus - remc_com));
Smax(dp[!cus2][com+1][ used],
dp[!cus2][com ][new_used] + profit);
} else {
Smax(dp[!cus2][com+1][used],
dp[ cus2][com ][ C] + profit);
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
read_input();
memset(dp[0], -32 /* -inf */, sizeof(dp[0]));
dp[0][0][C] = 0;
Loop (com,0,n) Loop (used,0,comps[com].c)
dp[0][com+1][used + C] = 0;
Loop (cus,0,m) {
const int cus2 = cus&1;
memset(dp[!cus2], -32 /* -inf */, sizeof(dp[!cus2]));
dp[!cus2][0][C] = 0;
Loop (com,0,n) Loop(used, -custs[cus].c + 1, comps[com].c) {
update_dp(cus+1, com+1, C + used);
}
}
cout << dp[m&1][n][C] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
5 ms |
3604 KB |
Output is correct |
4 |
Correct |
9 ms |
3608 KB |
Output is correct |
5 |
Correct |
76 ms |
3540 KB |
Output is correct |
6 |
Correct |
83 ms |
3608 KB |
Output is correct |
7 |
Correct |
85 ms |
3540 KB |
Output is correct |
8 |
Correct |
85 ms |
3600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
2 ms |
3540 KB |
Output is correct |
4 |
Correct |
2 ms |
3540 KB |
Output is correct |
5 |
Correct |
5 ms |
3540 KB |
Output is correct |
6 |
Correct |
3 ms |
3540 KB |
Output is correct |
7 |
Correct |
8 ms |
3540 KB |
Output is correct |
8 |
Correct |
8 ms |
3620 KB |
Output is correct |
9 |
Correct |
13 ms |
3540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
5 ms |
3540 KB |
Output is correct |
4 |
Correct |
6 ms |
3540 KB |
Output is correct |
5 |
Correct |
8 ms |
3540 KB |
Output is correct |
6 |
Correct |
7 ms |
3540 KB |
Output is correct |
7 |
Correct |
11 ms |
3540 KB |
Output is correct |
8 |
Correct |
12 ms |
3540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
5 ms |
3620 KB |
Output is correct |
4 |
Correct |
76 ms |
3604 KB |
Output is correct |
5 |
Correct |
803 ms |
3620 KB |
Output is correct |
6 |
Correct |
1367 ms |
3632 KB |
Output is correct |
7 |
Correct |
1373 ms |
3672 KB |
Output is correct |
8 |
Correct |
1316 ms |
3680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
6 ms |
3540 KB |
Output is correct |
3 |
Correct |
31 ms |
3540 KB |
Output is correct |
4 |
Correct |
79 ms |
3612 KB |
Output is correct |
5 |
Correct |
1035 ms |
3632 KB |
Output is correct |
6 |
Correct |
1388 ms |
3668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3540 KB |
Output is correct |
2 |
Correct |
2 ms |
3540 KB |
Output is correct |
3 |
Correct |
5 ms |
3604 KB |
Output is correct |
4 |
Correct |
9 ms |
3608 KB |
Output is correct |
5 |
Correct |
76 ms |
3540 KB |
Output is correct |
6 |
Correct |
83 ms |
3608 KB |
Output is correct |
7 |
Correct |
85 ms |
3540 KB |
Output is correct |
8 |
Correct |
85 ms |
3600 KB |
Output is correct |
9 |
Correct |
2 ms |
3540 KB |
Output is correct |
10 |
Correct |
2 ms |
3540 KB |
Output is correct |
11 |
Correct |
2 ms |
3540 KB |
Output is correct |
12 |
Correct |
2 ms |
3540 KB |
Output is correct |
13 |
Correct |
5 ms |
3540 KB |
Output is correct |
14 |
Correct |
3 ms |
3540 KB |
Output is correct |
15 |
Correct |
8 ms |
3540 KB |
Output is correct |
16 |
Correct |
8 ms |
3620 KB |
Output is correct |
17 |
Correct |
13 ms |
3540 KB |
Output is correct |
18 |
Correct |
2 ms |
3540 KB |
Output is correct |
19 |
Correct |
2 ms |
3540 KB |
Output is correct |
20 |
Correct |
5 ms |
3540 KB |
Output is correct |
21 |
Correct |
6 ms |
3540 KB |
Output is correct |
22 |
Correct |
8 ms |
3540 KB |
Output is correct |
23 |
Correct |
7 ms |
3540 KB |
Output is correct |
24 |
Correct |
11 ms |
3540 KB |
Output is correct |
25 |
Correct |
12 ms |
3540 KB |
Output is correct |
26 |
Correct |
2 ms |
3540 KB |
Output is correct |
27 |
Correct |
2 ms |
3540 KB |
Output is correct |
28 |
Correct |
5 ms |
3620 KB |
Output is correct |
29 |
Correct |
76 ms |
3604 KB |
Output is correct |
30 |
Correct |
803 ms |
3620 KB |
Output is correct |
31 |
Correct |
1367 ms |
3632 KB |
Output is correct |
32 |
Correct |
1373 ms |
3672 KB |
Output is correct |
33 |
Correct |
1316 ms |
3680 KB |
Output is correct |
34 |
Correct |
2 ms |
3540 KB |
Output is correct |
35 |
Correct |
6 ms |
3540 KB |
Output is correct |
36 |
Correct |
31 ms |
3540 KB |
Output is correct |
37 |
Correct |
79 ms |
3612 KB |
Output is correct |
38 |
Correct |
1035 ms |
3632 KB |
Output is correct |
39 |
Correct |
1388 ms |
3668 KB |
Output is correct |
40 |
Correct |
84 ms |
3540 KB |
Output is correct |
41 |
Correct |
279 ms |
3632 KB |
Output is correct |
42 |
Correct |
81 ms |
3668 KB |
Output is correct |
43 |
Correct |
1461 ms |
3676 KB |
Output is correct |
44 |
Correct |
1445 ms |
3684 KB |
Output is correct |
45 |
Correct |
1113 ms |
3720 KB |
Output is correct |
46 |
Correct |
51 ms |
3628 KB |
Output is correct |
47 |
Correct |
82 ms |
3584 KB |
Output is correct |
48 |
Correct |
75 ms |
3668 KB |
Output is correct |