Submission #680670

#	Time	Username	Problem	Language	Result	Execution time	Memory
680670		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	212 KiB

cake3

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, m;
multiset<int> s, s_;
struct _ {
    int v, c;
} x[N];
int cur = 0;
bool cmp(_ a, _ b) {
    return (a.c < b.c);
}
void add(int id) {
    s_.insert(x[id].v);
    cur += x[id].v;
    if(s_.size() == m + 1) {
        s.insert(*s_.begin());
        cur -= *s_.begin();
        s_.erase(s_.find(*s_.begin()));
    }
}
void rem(int id) {
    if(s.find(x[id].v) != s.end()) {
        s.erase(s.find(x[id].v));
        return;
    }
    assert(s_.find(x[id].v) != s_.end());
    s_.erase(s_.find(x[id].v));
    cur -= x[id].v;
    if(s.size()) {
        cur += *--s.end();
        s_.insert(*--s.end());
        s.erase(s.find(*--s.end()));
    }
}
main(){
    int n;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].v >> x[i].c;
    }
    sort(x + 1, x + n + 1, cmp);

    queue< pair<pii, pii> > st;

    st.push({{m, n}, {1, n}});
    int L = 0, R = 0, ans = 0;
    while(st.size()) {
        int l = st.front().f.f, r = st.front().f.s, optl = st.front().s.f, optr = st.front().s.s;
        st.pop();
        int mid = (l + r) / 2;
        //if(R > mid)
        {
            cur = 0; L = 0; R = 0;
            while(s.size()) s.erase(*s.begin());
            while(s_.size()) s_.erase(*s_.begin());
        }
//        cout << L << " __ _ __" << " " << R << endl;
        // optl .. min(mid - m + 1, optr) gvawyobs
        /*
        while(R < mid) {
            ++R;
            add(R);
        }
        while(L < min(optr, mid - m + 1)) {
           if(L) rem(L);
            ++L;
        } */

        for(int i = min(optr, mid - m + 1); i <= mid; i++) add(i);
       assert(optl <= min(optr, mid - m + 1));
        int X = cur - (x[mid].c - x[min(optr, mid - m + 1)].c) * 2, opt = min(optr, mid - m + 1);

        for(int i = min(optr, mid - m + 1) - 1; i >= optl; i--) {
            add(i);
            if(cur - (x[mid].c - x[i].c) * 2 > X) opt = i, X = cur - (x[mid].c - x[i].c) * 2;
        }
        L = optl;
        ans = max(ans, X);

        if(l < mid) st.push({{l, mid - 1},{optl, opt}});
        if(mid < r) st.push({{mid + 1, r}, {opt, optr}});
    }

    cout << ans;


 }

Compilation message (stderr)

cake3.cpp: In function 'void add(long long int)':
cake3.cpp:20:18: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |     if(s_.size() == m + 1) {
      |        ~~~~~~~~~~^~~~~~~~
cake3.cpp: At global scope:
cake3.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:51:9: warning: variable 'L' set but not used [-Wunused-but-set-variable]
   51 |     int L = 0, R = 0, ans = 0;
      |         ^
cake3.cpp:51:16: warning: variable 'R' set but not used [-Wunused-but-set-variable]
   51 |     int L = 0, R = 0, ans = 0;
      |                ^

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