Submission #1014482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014482		vjudge1	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	604 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> cake;
int ans;

int dostuf(int pen){
    ans = 0;
    map<int, pair<int, int>> mp;
    for (auto [i, j] : cake) {
        if (j >= pen) {
            mp[i].first += j - pen;
            mp[i].second--;
        }
    }
    if (mp.empty()) return 0;

    int prv = mp.begin()->first;
    pair<int, int> mmin = {0, 0}, now = {0, 0}, bst = {0, 0};

    for (auto& [i, j] : mp) {
        j.first -= 2 * i - 2 * prv;
        prv = i;
        now.first += j.first;
        now.second += j.second;
        mmin = min(mmin, now);
        bst = max(bst, {now.first - mmin.first, now.second - mmin.second});
    }

    ans = bst.first;
    return -bst.second;
}

signed main() {
    int n, m;
    cin >> n >> m;
    cake.resize(n);
    for (auto& [i, j] : cake)
        cin >> j >> i;

    int l = -1e9, r = 1e9, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (dostuf(mid) >= m) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    dostuf(res);
    cout << ans + res * m;
}

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