Submission #796535

#	Time	Username	Problem	Language	Result	Execution time	Memory
796535		thimote75	Cake 3 (JOI19_cake3)	C++14	24 / 100	4057 ms	20528 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define p_be second
#define p_ta first
    
using namespace std;
    
using idata = vector<int>;
using t_perle = pair<int, int>;
using t_perles = vector<t_perle>;
    
signed main () {
    int N, M;
    cin >> N >> M;
    
    t_perles perles;
    set<int> beauty_set;
    for (int i = 0; i < N; i ++) {
        int b, t;
        cin >> b >> t;
    
        beauty_set.insert(b);
        perles.push_back({ t, b });
    }
    
    idata beauty_unique;
    for (int u : beauty_set) beauty_unique.push_back(u);
    
    sort(perles.begin(), perles.end());
    
    idata beauty;
    for (const auto &perle : perles)
        beauty.push_back(perle.p_be);
        
    int max_result = -1e18;
    for (int left = 0; left < N; left ++) {
        priority_queue<int> vs; int sum = 0;
        for (int i = left; i <= left + M - 1; i ++) {
            sum += beauty[i];
            vs.push(- beauty[i]);
        }
        for (int right = left + M - 1; right < N; right ++) {
            int low = - vs.top();
            if (low < beauty[right] && right != left + M - 1) {
                vs.pop();
                sum -= low;
                sum += beauty[right];
                vs.push(-beauty[right]);
            }            
            int result = 2 * (perles[left].p_ta - perles[right].p_ta) + sum;
            max_result = max(max_result, result);
        }
    }
    
    cout << max_result << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76