이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* 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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |