Submission #377159

#	Time	Username	Problem	Language	Result	Execution time	Memory
377159		jass921026	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	364 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
const ll MAXN=2E5+10, INF=1E18;
int n, m;
pii cake[MAXN];
ll ans[MAXN];
priority_queue<int,vector<int>,greater<int> > pq;
void solve(int l, int r, int ll, int rr){
    if(l>=r) return;
    int mid=(l+r)/2, p=0;
    while(!pq.empty()) pq.pop();
    long long penalty=0, sum=0;
    for(int i=ll;i<=rr;i++){
        if(i<mid) continue;
        penalty=2*(cake[i].F-cake[mid].F);
        if(pq.size()<m){
            pq.push(cake[i].S);
            sum+=cake[i].S;
        } else if(cake[i].S>pq.top()){
            sum=sum-pq.top()+cake[i].S;
            pq.pop();
            pq.push(cake[i].S);
        }
        if(pq.size()==m&&sum-penalty>ans[mid]){
            ans[mid]=sum-penalty;
            p=i;
        }
    }
    solve(l,mid-1,ll,p);
    solve(mid+1,r,p,rr);
}
int main(){ jizz
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>cake[i].S>>cake[i].F;
    }
    sort(cake,cake+n);
    for(int i=0;i<n;i++) ans[i]=-INF;
    solve(0,n-m,0,n-1);
    ll ANS=-INF;
    for(int i=0;i<n;i++) ANS=max(ANS,ans[i]);
    cout<<ANS<<"\n";
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:21:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |         if(pq.size()<m){
      |            ~~~~~~~~~^~
cake3.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         if(pq.size()==m&&sum-penalty>ans[mid]){
      |            ~~~~~~~~~^~~

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