Submission #592663

#	Time	Username	Problem	Language	Result	Execution time	Memory
592663		79brue	Cake 3 (JOI19_cake3)	C++17	0 / 100	0 ms	212 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
pair<ll, ll> arr[200002]; /// (C, V)
ll ans;

void updateAns(vector<ll> &vl, vector<ll> &vr){
    if((int)vl.size() + (int)vr.size() < k) return;
    for(int i=0; i<(int)vl.size(); i++){
        int j = k - i - 2;
        if(j<0 || j>=(int)vr.size()) continue;
        ans = max(ans, vl[i] + vr[j]);
    }
}

void updateRet(vector<ll> &ret, vector<ll> &base, vector<ll> &add){
    ret.push_back(base[0]);
    int lpnt = 1, rpnt = 0;
    ll lval = base[0], rval = 0;
    while((int)ret.size() < (int)base.size() + (int)add.size()){
        if(lpnt == (int)base.size() || lpnt == k-2){
            rval = add[rpnt++];
        }
        else if(rpnt == (int)add.size() || rpnt == k-2){
            lval = base[lpnt++];
        }
        else if(base[lpnt] - lval >= add[rpnt] - rval){
            lval = base[lpnt++];
        }
        else{
            rval = add[rpnt++];
        }
        ret.push_back(lval + rval);
    }
}

void dnc(int l, int r, vector<ll> &vLeft, vector<ll> &vRight){
    if(l==r){
        vLeft.push_back(arr[l].second + arr[l].first*2);
        vRight.push_back(arr[l].second - arr[l].first*2);
        return;
    }
    vector<ll> lLeft, lRight;
    vector<ll> rLeft, rRight;
    int m = (l+r)>>1;
    dnc(l, m, lLeft, lRight);
    dnc(m+1, r, rLeft, rRight);
    updateAns(lLeft, rRight);

    vector<ll> lElem, rElem;
    for(int i=l; i<=m; i++) lElem.push_back(arr[i].second);
    for(int i=m+1; i<=r; i++) rElem.push_back(arr[i].second);
    sort(lElem.rbegin(), lElem.rend());
    sort(rElem.rbegin(), rElem.rend());
    for(int i=1; i<(int)lElem.size(); i++) lElem[i] += lElem[i-1];
    for(int i=1; i<(int)rElem.size(); i++) rElem[i] += rElem[i-1];

    /// vl 업데이트
    updateRet(vLeft, lLeft, rElem);
    updateRet(vRight, rRight, lElem);
    for(int i=0; i<(int)rLeft.size(); i++) vLeft[i] = max(vLeft[i], rLeft[i]);
    for(int i=0; i<(int)lRight.size(); i++) vRight[i] = max(vRight[i], lRight[i]);
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &arr[i].second, &arr[i].first);
    }
    sort(arr+1, arr+n+1);
    vector<ll> dummy1, dummy2;
    dnc(1, n, dummy1, dummy2);
    printf("%lld", ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%lld %lld", &arr[i].second, &arr[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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