Submission #770699

#	Time	Username	Problem	Language	Result	Execution time	Memory
770699		treewave	Cloud Computing (CEOI18_clo)	C++17	0 / 100	3079 ms	262144 KiB

clo

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int INF = 1e18;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<array<int,3>> computers;
    for (int i = 0; i < n; i++){
        int cores, clock, price;
        cin >> cores >> clock >> price;
        computers.push_back({clock, cores, price});
    }
    int m; cin >> m;
    vector<array<int,3>> customers;
    for (int i = 0; i < m; i++){
        int cores, clock, price;
        cin >> cores >> clock >> price;
        customers.push_back({clock, cores, price});
    }
    sort(computers.begin(), computers.end());
    sort(customers.begin(), customers.end());
    vector<int> freq_computers;
    for (int i = 0; i < m; i++){
        freq_computers.push_back(computers[i][0]);
    }
    vector<array<int, 2>> computer_ranges;
    //want to store for each customer adjacent pair, the range of computers with freq in [freq[i], freq[i+1])
    //this naturally ignores the instances where freq[i] == freq[i+1], so we don't have to worry about overcount
    for (int i = 0; i < m-1; i++){
        int lb = lower_bound(freq_computers.begin(), freq_computers.end(), customers[i][0]) - freq_computers.begin();
        int ub = lower_bound(freq_computers.begin(), freq_computers.end(), customers[i+1][0]) - freq_computers.begin();
        if (lb == n || lb > ub){
            computer_ranges.push_back({-1, -1});
            continue;
        }
        ub--;
        computer_ranges.push_back({lb, ub});
    }
    int final_lb = lower_bound(freq_computers.begin(), freq_computers.end(), customers.back()[0]) - freq_computers.begin();
    if (final_lb != n){
        computer_ranges.push_back({final_lb, n-1});
    }
    else{
        computer_ranges.push_back({-1, -1});
    }
//    for (int i = 0; i < m; i++){
//        cout << computer_ranges[i][0] << " " << computer_ranges[i][1] << "\n";
//    }

    //bounding to get subtasks
    int maxCores = 0;
    int temp = 0;
    for (int i = 0; i < m; i++){
        temp += customers[i][1];
    }
    maxCores = max(maxCores, temp);
    temp = 0;
    for (int i = 0; i < n; i++){
        temp += computers[i][1];
    }
    maxCores = max(maxCores, temp);
    maxCores++;
    vector<vector<int>> minCost(m, vector<int>(maxCores, INF));
    vector<vector<int>> newMinCost(m, vector<int> (maxCores, INF));
    for (int i = 0; i < m; i++){
        int lb = computer_ranges[i][0], ub = computer_ranges[i][1];
        if (lb == -1) continue;
        minCost[i][0] = 0;
        for (int j = lb; j <= ub; j++){
            for (int k = computers[j][1]; k < maxCores; k++){
                newMinCost[i][k] = min(minCost[i][k], minCost[i][k - computers[j][1]] + computers[j][2]);
            }
            for (int k = computers[j][1]; k < maxCores; k++){
                minCost[i][k] = newMinCost[i][k];
            }
            //suffix min
            int currMin = INF;
            for (int k = maxCores-1; k >= 0; k--){
                minCost[i][k] = min(minCost[i][k], currMin);
                currMin = min(currMin, minCost[i][k]);
            }
        }
    }
    vector<vector<int>> dp(m+1, vector<int> (maxCores, -INF));
    vector<vector<int>> newdp(m+1, vector<int>(maxCores, -INF));
    //dp[i][c] is maximum profit using suffix [i,....,m-1] and having c extra cores
    dp[m][0] = 0;
    for (int i = 0; i < maxCores; i++){
        dp[m][i] = max(dp[m][i], -minCost[m-1][i]);
    }
    //suffix max
    int currMax = -INF;
    for (int i = maxCores-1; i >= 0; i--){
        dp[m][i] = max(dp[m][i], currMax);
        currMax = max(currMax, dp[m][i]);
    }
    for (int i = m-1; i >= 0; i--){
        for (int c = 0; c < maxCores - customers[i][1]; c++){
            dp[i][c] = max(dp[i+1][c], dp[i+1][c + customers[i][1]] + customers[i][2]);
        }
        currMax = -INF;
        for (int j = maxCores-1; j >= 0; j--){
            dp[i][j] = max(dp[i][j], currMax);
            currMax = max(currMax, dp[i][j]);
        }
        //add cores from new computers
        if (i != 0){
            for (int j = 0; j < maxCores; j++){
                newdp[i][j] = -INF;
            }
            for (int j = 0; j < maxCores; j++){
                for (int x = 0; x < maxCores - j; x++){
                    newdp[i][j+x] = max({newdp[i][j+x], dp[i][j+x], dp[i][j] - minCost[i-1][x]});
                }
            }
            for (int j = 0; j < maxCores; j++){
                dp[i][j] = newdp[i][j];
            }
        }
        currMax = -INF;
        for (int j = maxCores-1; j >= 0; j--){
            dp[i][j] = max(dp[i][j], currMax);
            currMax = max(currMax, dp[i][j]);
        }
    }
    int ans = -INF;
    for (int i = 0; i < maxCores; i++){
        ans = max(ans, dp[0][i]);
    }
    cout << ans << "\n";
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 18
• Subtask 3: 0 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10