oj.uz

Submission #622337

# Submission time Handle Problem Language Result Execution time Memory
622337 2022-08-04T07:33:56 Z jophyyjh Cloud Computing (CEOI18_clo) C++14
100 / 100
 2899 ms 2012 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, 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';
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory 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