| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 622279 |
2022-08-04T05:47:00 Z |
jophyyjh |
Lottery (CEOI18_lot) |
C++14 |
|
34 ms |
65536 KB |
/**
* 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)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
const int_t NM_MAX = 2000;
const int_t C_MAX = 50;
const int_t INF = 0x3f3f3f3f3f3f3f;
struct mach_t {
int_t cores, speed, price;
};
struct order_t {
int_t cores, speed, budg;
};
int_t dp[2][NM_MAX + 1][C_MAX + 1]; // optimize memory usage
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int_t n, m;
std::cin >> n;
std::vector<mach_t> machs(n);
for (int_t 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_t 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 (int_t i = 0; i < 2; i++) {
for (int_t j = 0; j <= m; j++) {
for (int_t c = 0; c <= C_MAX; c++)
dp[i][j][c] = -INF;
}
}
dp[0][0][0] = 0;
for (int_t i = 0; i <= n; i++) {
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 (int_t j = 0; j <= m; j++) {
for (int_t c = 0; c <= C_MAX; c++) {
if (i < n)
dp[(i + 1) % 2][j][c] = std::max(dp[(i + 1) % 2][j][c], dp[i % 2][j][c]);
if (j < m)
dp[i % 2][j + 1][c] = std::max(dp[i % 2][j + 1][c], dp[i % 2][j][c]);
if (i < n) {
int_t d = (c + machs[i].cores) % C_MAX;
dp[(i + 1) % 2][j][d] = std::max(dp[(i + 1) % 2][j][d], dp[i % 2][j][c] - machs[i].price);
}
if (i > 0 && j < m && c >= orders[j].cores && machs[i - 1].speed >= orders[j].speed) {
int_t d = c - orders[j].cores;
dp[i % 2][j + 1][d] = std::max(dp[i % 2][j + 1][d], dp[i % 2][j][c] + orders[j].budg);
}
if (i < n && j < m && c + machs[i].cores >= orders[j].cores
&& machs[i].speed >= orders[j].speed) {
int_t d = (c + machs[i].cores - orders[j].cores) % C_MAX;
dp[(i + 1) % 2][j + 1][d] = std::max(dp[(i + 1) % 2][j + 1][d],
dp[i % 2][j][c] + orders[j].budg - machs[i].price);
}
}
}
}
// for (int_t i = 0; i <= n; i++) {
// for (int_t j = 0; j <= m; j++) {
// std::cerr << i << ' ' << j << ": ";
// for (int_t c = 0; c <= C_MAX; c++)
// std::cerr << dp[i][j][c] << ' ';
// std::cerr << std::endl;
// }
// }
int_t profit = -INF;
for (int_t c = 0; c <= C_MAX; c++)
profit = std::max(profit, dp[n % 2][m][c]);
std::cout << profit << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
