Submission #377158

#	Time	Username	Problem	Language	Result	Execution time	Memory
377158		jass921026	Cake 3 (JOI19_cake3)	C++14	24 / 100	183 ms	524 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=2E3+10, INF=1E18;
pii cake[MAXN];
priority_queue<int,vector<int>,greater<int> > pq;
int main(){ jizz
    int n, m;
    cin>>n>>m;
    if(n>MAXN) return 0;
    for(int i=0;i<n;i++){
        cin>>cake[i].S>>cake[i].F;
    }
    sort(cake,cake+n);
    ll ans=-INF;
    for(int i=0;i<n;i++){
        ll penalty=0, sum=0, res=-INF;
        while(!pq.empty()) pq.pop();
        for(int j=i;j<n;j++){
            penalty=2*(cake[j].F-cake[i].F);
            if(pq.size()<m){
                sum+=cake[j].S;
                pq.push(cake[j].S);
            } else if(cake[j].S>pq.top()){
                sum=sum-pq.top()+cake[j].S;
                pq.pop();
                pq.push(cake[j].S);
            }
            if(pq.size()==m) res=max(res,sum-penalty);
        }
        ans=max(ans,res);
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:25:25: 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]
   25 |             if(pq.size()<m){
      |                ~~~~~~~~~^~
cake3.cpp:33:25: 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]
   33 |             if(pq.size()==m) res=max(res,sum-penalty);
      |                ~~~~~~~~~^~~

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