Submission #138923

#	Time	Username	Problem	Language	Result	Execution time	Memory
138923		zoooma13	Cake 3 (JOI19_cake3)	C++14	24 / 100	4016 ms	5536 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int ,int>
#define c first
#define v second

int n ,m;
vector <pii> pcs;

long long query(int i ,int j){
    long long ret = -2*(pcs[j].c-pcs[i].c)+pcs[i].v+pcs[j].v;
    priority_queue <long long> pq;
    for(int k=i+1; k<j; k++)
        pq.push(pcs[k].v);
    for(int k=2; k<m; k++)
        ret += pq.top() ,pq.pop();
    return ret;
}

long long ans = -1e18;
void solve(int l ,int r ,int i ,int j){
    if(j < i) return;

    int mid = (i+j)>>1;
    long long opt_v = -1e18 ,curr;
    int opt_k = l;
    for(int k=l; k<=r; k++){
        if(k > mid-m+1)
            break;
        curr = query(k ,mid);
        if(curr >= opt_v){
            opt_v = curr;
            opt_k = k;
        }
    }

    ans = max(ans ,opt_v);
    solve(l ,opt_k ,i ,mid-1);
    solve(opt_k ,r ,mid+1 ,j);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int a,b,i=0; i<n; i++){
        scanf("%d%d",&a,&b);
        pcs.push_back({b,a});
    }

    sort(pcs.begin() ,pcs.end());
    solve(0 ,n-1 ,m-1 ,n-1);
    printf("%lld",ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
cake3.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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