Submission #622337

#	Time	Username	Problem	Language	Result	Execution time	Memory
622337		jophyyjh	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2899 ms	2012 KiB

clo

/**
 * 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 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10