제출 #680734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680734		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++14	24 / 100	4074 ms	11112 KiB

cake3

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
const ll inf = 1e18; // !
int t, m, OPE = 0;
multiset<int> s, s_;
struct _ {
    int v, c;
} x[N];
ll 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(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    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, F = 0;
    ll ans = -inf;
    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;
            s.clear();
            s_.clear();
        }
//        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;
        }
        assert(L == min(optr, mid - m + 1));
        assert(R == mid);
        ll X = cur - (x[mid].c - x[min(optr, mid - m + 1)].c) * 2, opt = min(optr, mid - m + 1);
        OPE += min(optr, mid - m + 1) - 1 - optl + 1;
        assert(OPE <= n * 20);
        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;


 }

컴파일 시 표준 에러 (stderr) 메시지

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

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