Submission #263330

#	Time	Username	Problem	Language	Result	Execution time	Memory
263330		keko37	Cake 3 (JOI19_cake3)	C++14	24 / 100	4043 ms	11496 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 200005;
const llint INF = 1000000000000000000LL;

llint n, m, sum, sol = -INF;
pi p[MAXN];
multiset <int> st;
vector <pi> v;

bool cmp (pi a, pi b) {
    return a.second < b.second;
}

void ubaci (int val) {
    //cout << "ubaci " << val << endl;
    st.insert(val);
    sum += val;
    if (st.size() > m - 2) {
        auto it = st.begin();
        sum -= *it;
        v.push_back({val, *it});
        st.erase(it);
    } else {
        v.push_back({val, 0});
    }
}

void rollback () {
    int val = v.back().first, mn = v.back().second;
    //cout << "rollback " << val << " " << mn << endl;
    v.pop_back();
    if (mn) st.insert(mn);
    st.erase(st.find(val));
    sum += mn - val;
}

void calc (int lef, int rig, int lo, int hi) {
    if (lef > rig) return;
    //cout << "calc " << lef << " " << rig << " " << lo << " " << hi << endl;
    int mid = (lef + rig) / 2;
    //cout << "mid je " << mid << endl;
    for (int i = max(hi + 1, lef); i < mid; i++) {
        ubaci(p[i].first);
    }
    llint res = -INF, piv = -1;
    for (int i = min(mid - 1, hi); i >= lo; i--) {
        if (st.size() == m - 2) {
            llint tmp = sum + p[i].first + p[i].second;
            if (tmp > res) {
                res = tmp;
                piv = i;
            }
        }
        ubaci(p[i].first);
    }
    //cout << "piv je " << piv << endl;
    sol = max(sol, res + p[mid].first - p[mid].second);

    for (int i = lo; i <= min(mid - 1, hi); i++) rollback();
    if (hi < mid) ubaci(p[mid].first);
    calc(mid + 1, rig, piv, hi);
    if (hi < mid) rollback();

    for (int i = max(hi + 1, lef); i < mid; i++) rollback();
    for (int i = piv + 1; i <= min(lef - 1, hi); i++) ubaci(p[i].first);
    calc(lef, mid - 1, lo, piv);
    for (int i = piv + 1; i <= min(lef - 1, hi); i++) rollback();
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        p[i].second *= 2;
    }
    sort(p, p + n, cmp);
    calc(m - 1, n - 1, 0, n - 1);
    cout << sol;
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void ubaci(int)':
cake3.cpp:24:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'llint' {aka 'long long int'} [-Wsign-compare]
   24 |     if (st.size() > m - 2) {
      |         ~~~~~~~~~~^~~~~~~
cake3.cpp: In function 'void calc(int, int, int, int)':
cake3.cpp:53:23: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'llint' {aka 'long long int'} [-Wsign-compare]
   53 |         if (st.size() == m - 2) {
      |             ~~~~~~~~~~^~~~~~~~

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