Submission #140128

#	Time	Username	Problem	Language	Result	Execution time	Memory
140128		KLPP	Cake 3 (JOI19_cake3)	C++14	24 / 100	4066 ms	7480 KiB

cake3

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 1000000000000000000

int main(){
  int n,m;
  scanf("%d %d",&n,&m);
  pii cakes[n];
  rep(i,0,n){
    scanf("%lld %lld",&cakes[i].second,&cakes[i].first);
  }
  sort(cakes,cakes+n);
  //rep(i,0,n)cout<<cakes[i].first<<" "<<cakes[i].second<<endl;
  lld ans=-INF;
  rep(i,0,n){
    priority_queue<lld> pq;
    lld sum=0;
    rep(j,i,n){
      sum+=cakes[j].second;
      pq.push(-cakes[j].second);
      while(pq.size()>m){
	sum+=pq.top();pq.pop();
      }
      //cout<<sum+2*cakes[i].first-2*cakes[j].first<<endl;
      if(pq.size()==m)ans=max(ans,sum+2*cakes[i].first-2*cakes[j].first);
    }
  }
  
  printf("%lld\n",ans);
  /*rep(i,0,(1<<n)){
    vector<int> v;
    rep(j,0,n){
      if(((1<<j)&i)>0){
	v.push_back(j);
      }
    }
    if(v.size()==m){
      lld sum=0;
      lld Max=-INF;
      lld Min=INF;
      trav(a,v){
	Max=max(Max,cakes[v[a]].first);
	Min=min(Min,cakes[v[a]].first);
	sum+=cakes[v[a]].second;
      }
      if(sum-2*(Max-Min)==2323231661){
	trav(a,v)cout<<a<<endl;
      }
    }
  }*/
  return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while(pq.size()>m){
             ~~~~~~~~~^~
cake3.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(pq.size()==m)ans=max(ans,sum+2*cakes[i].first-2*cakes[j].first);
          ~~~~~~~~~^~~
cake3.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&cakes[i].second,&cakes[i].first);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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