/**
* Notes during contest.
*
* ------ A ------
* Looks like a dp, and the score distribution is interesting too.. Sort the machines
* and orders by their clock speed. By greedy arguments, if we've seletected the
* subset of orders & machines, we sort the clock speed in order and assign them.
* [S3] is the one that gave me the idea: we first sort orders & machines, then use
* O(nm) dp on prefixes. Note that cores can be shared across orders, so we need an
* additional val in our dp state, which is the num of cores left. This val can at
* most be 50. Note that one should take a close look at the memory limit too: our dp
* sequence shouldn't take up too much memory.
*
* P.S. When about 1.5 hours were left, I left home. Technically I didn't finish the
* virtual contest.
*
* ------ B ------
* I think i've seen sth similar on luogu. First, let's assume that d >= 0 and i'll
* use the words "increase" & "decrease". If we wanna increase an interval by d, we
* can greedily increase a suffix (instead of just an interval in the middle). If we
* are to decrease an interval by d, we can greedily decrease a prefix. The two cases
* are symmetric, so we can assume that one always increase a suffix by 0 <= d <= x.
* And, if we're increasing a suffix, why don't we just do d=x? The rest is quite
* straight-forward.
*
* ------ C ------
* For k_j = 0, we have to find the num of times each interval appeared. This can be
* effectively done with str hashing. [S3] solved. [S1] is just brute-force: we can
* do a O(n^2) for loop, iterating over all pairs of starting pos, naively comparing
* the dist. of 2 substr. [S2] is a O(n^2) comparison between pairs of VALUES and
* apply a difference array.
* We're only looking for the num of mismatches. Let's compress the values (a_i:
* 10^9 -> 10^4).
*
* Time Complexity 1: O(nm * c_max + n * log(n) + m * log(m))
* Time Complexity 2: O(n * log(n))
* Time Complexity 3: O(n^2 + q) ([S1-2]), O(n) (non-deterministic hashing)
* Implementation 1 (Full solution, dp + greedy, slightly optimized)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
const int NM_MAX = 2000;
const int C_MAX = 50;
const int_t INF = 0x3f3f3f3f3f3f3f;
struct mach_t {
int cores, speed, price;
};
struct order_t {
int cores, speed, budg;
};
int_t dp[2][NM_MAX + 1][C_MAX]; // optimize memory usage
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
std::cin >> n;
std::vector<mach_t> machs(n);
for (int k = 0; k < n; k++)
std::cin >> machs[k].cores >> machs[k].speed >> machs[k].price;
std::cin >> m;
std::vector<order_t> orders(m);
for (int k = 0; k < m; k++)
std::cin >> orders[k].cores >> orders[k].speed >> orders[k].budg;
std::sort(machs.begin(), machs.end(),
[](const mach_t& m1, const mach_t& m2) {
return m1.speed > m2.speed;
});
std::sort(orders.begin(), orders.end(),
[](const order_t& o1, const order_t& o2) {
return o1.speed > o2.speed;
});
for (register int i = 0; i < 2; i++) {
for (register int j = 0; j <= m; j++) {
for (register int c = 0; c < C_MAX; c++)
dp[i][j][c] = -INF;
}
}
dp[0][0][0] = 0;
for (register int i = 0; i <= n; i++) {
// // Not necessary: dp[i+2][j][c] >= dp[i][j][c]
// for (int_t j = 0; j <= m; j++) {
// for (int_t c = 0; c <= C_MAX; c++) {
// dp[(i + 1) % 2][j][c] = -INF;
// }
// }
for (register int j = 0; j <= m; j++) {
for (register int c = 0; c < C_MAX; c++) {
if (i < n)
dp[(i + 1) & 1][j][c] = std::max(dp[(i + 1) & 1][j][c], dp[i & 1][j][c]);
if (j < m)
dp[i & 1][j + 1][c] = std::max(dp[i & 1][j + 1][c], dp[i & 1][j][c]);
register int d;
if (i < n) {
d = (c + machs[i].cores) % C_MAX;
dp[(i + 1) & 1][j][d] = std::max(dp[(i + 1) & 1][j][d], dp[i & 1][j][c] - machs[i].price);
}
d = c - orders[j].cores; // Overflow happens, but just read
if (i > 0 && j < m && d >= 0 && machs[i - 1].speed >= orders[j].speed)
dp[i & 1][j + 1][d] = std::max(dp[i & 1][j + 1][d], dp[i & 1][j][c] + orders[j].budg);
d = c + machs[i].cores - orders[j].cores; // Overflow happens, but just read
if (i < n && j < m && d >= 0 && d < C_MAX && machs[i].speed >= orders[j].speed) {
dp[(i + 1) & 1][j + 1][d] = std::max(dp[(i + 1) & 1][j + 1][d],
dp[i & 1][j][c] + orders[j].budg - machs[i].price);
}
}
}
}
int_t profit = -INF;
for (register int c = 0; c < C_MAX; c++)
profit = std::max(profit, dp[n & 1][m][c]);
std::cout << profit << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
20 ms |
1876 KB |
Output is correct |
6 |
Correct |
24 ms |
1796 KB |
Output is correct |
7 |
Correct |
21 ms |
1944 KB |
Output is correct |
8 |
Correct |
21 ms |
1952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
9 ms |
340 KB |
Output is correct |
6 |
Correct |
8 ms |
340 KB |
Output is correct |
7 |
Correct |
20 ms |
412 KB |
Output is correct |
8 |
Correct |
20 ms |
340 KB |
Output is correct |
9 |
Correct |
22 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
6 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
420 KB |
Output is correct |
5 |
Correct |
27 ms |
436 KB |
Output is correct |
6 |
Correct |
27 ms |
432 KB |
Output is correct |
7 |
Correct |
48 ms |
520 KB |
Output is correct |
8 |
Correct |
44 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
8 ms |
332 KB |
Output is correct |
4 |
Correct |
20 ms |
1784 KB |
Output is correct |
5 |
Correct |
2609 ms |
1796 KB |
Output is correct |
6 |
Correct |
2899 ms |
1960 KB |
Output is correct |
7 |
Correct |
2842 ms |
2004 KB |
Output is correct |
8 |
Correct |
2789 ms |
1932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
4 ms |
340 KB |
Output is correct |
3 |
Correct |
88 ms |
468 KB |
Output is correct |
4 |
Correct |
826 ms |
1296 KB |
Output is correct |
5 |
Correct |
2467 ms |
1976 KB |
Output is correct |
6 |
Correct |
2788 ms |
1940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
20 ms |
1876 KB |
Output is correct |
6 |
Correct |
24 ms |
1796 KB |
Output is correct |
7 |
Correct |
21 ms |
1944 KB |
Output is correct |
8 |
Correct |
21 ms |
1952 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
328 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
9 ms |
340 KB |
Output is correct |
14 |
Correct |
8 ms |
340 KB |
Output is correct |
15 |
Correct |
20 ms |
412 KB |
Output is correct |
16 |
Correct |
20 ms |
340 KB |
Output is correct |
17 |
Correct |
22 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
328 KB |
Output is correct |
19 |
Correct |
1 ms |
328 KB |
Output is correct |
20 |
Correct |
6 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
420 KB |
Output is correct |
22 |
Correct |
27 ms |
436 KB |
Output is correct |
23 |
Correct |
27 ms |
432 KB |
Output is correct |
24 |
Correct |
48 ms |
520 KB |
Output is correct |
25 |
Correct |
44 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
8 ms |
332 KB |
Output is correct |
29 |
Correct |
20 ms |
1784 KB |
Output is correct |
30 |
Correct |
2609 ms |
1796 KB |
Output is correct |
31 |
Correct |
2899 ms |
1960 KB |
Output is correct |
32 |
Correct |
2842 ms |
2004 KB |
Output is correct |
33 |
Correct |
2789 ms |
1932 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
4 ms |
340 KB |
Output is correct |
36 |
Correct |
88 ms |
468 KB |
Output is correct |
37 |
Correct |
826 ms |
1296 KB |
Output is correct |
38 |
Correct |
2467 ms |
1976 KB |
Output is correct |
39 |
Correct |
2788 ms |
1940 KB |
Output is correct |
40 |
Correct |
159 ms |
724 KB |
Output is correct |
41 |
Correct |
572 ms |
1284 KB |
Output is correct |
42 |
Correct |
1596 ms |
1560 KB |
Output is correct |
43 |
Correct |
2770 ms |
1976 KB |
Output is correct |
44 |
Correct |
2730 ms |
1980 KB |
Output is correct |
45 |
Correct |
2430 ms |
2012 KB |
Output is correct |
46 |
Correct |
702 ms |
1228 KB |
Output is correct |
47 |
Correct |
1558 ms |
1572 KB |
Output is correct |
48 |
Correct |
1508 ms |
1620 KB |
Output is correct |