Submission #108032

#	Time	Username	Problem	Language	Result	Execution time	Memory
108032		dragonslayerit	Cake 3 (JOI19_cake3)	C++14	24 / 100	4027 ms	15828 KiB

cake3

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
#include <stdint.h>

const int64_t INF=1e15+7;

std::vector<std::pair<int64_t,int64_t> > cake;

int64_t N,M;

struct DataStruct{
  std::multiset<int> low,high;
  int64_t ll,rr;//(ll,rr) for elements, [ll,rr] for query
  int64_t high_sum;
  DataStruct():ll(0),rr(1),high_sum(0){
  }
  void up(){
    high_sum+=*low.rbegin();
    high.insert(*low.rbegin());
    low.erase(low.find(*low.rbegin()));
  }
  void down(){
    high_sum-=*high.begin();
    low.insert(*high.begin());
    high.erase(high.begin());
  }
  void balance(){
    while(low.size()&&high.size()<M-2){
      up();
    }
    while(high.size()>M-2){
      down();
    }
    while(low.size()&&high.size()&&*low.rbegin()>*high.begin()){
      up();
      down();
    }
  }
  void add(int64_t i){
    int64_t x=cake[i].second;
    low.insert(x);
  }
  void rem(int64_t i){
    int64_t x=cake[i].second;
    if(low.count(x)){
      low.erase(low.find(x));
    }else{
      assert(high.count(x));
      high_sum-=x;
      high.erase(high.find(x));
    }
  }
  int64_t query(int64_t l,int64_t r){
    if(r-l+1<M) return -INF;
    while(ll>l) add(ll--);
    while(rr<r) add(rr++);
    while(ll<l) rem(++ll);
    while(rr>r) rem(--rr);
    balance();
    assert(high.size()+low.size()==r-l-1);
    return high_sum+cake[l].second+cake[r].second+2LL*(cake[l].first-cake[r].first);
  }
  void dump(){
    for(int64_t x:low) printf("%ld ",x);
    printf("|");
    for(int64_t x:high) printf(" %ld",x);
    printf("\n");
  }
}ds;

int64_t best=-INF;

//find ans for (l,r), which must be in range [low,high]
void solve(int64_t l,int64_t r,int64_t low,int64_t high){
  if(r-l<=1) return;
  int64_t m=(l+r)/2;
  int64_t max=-INF;
  int64_t maxi=-1;
  for(int64_t i=low;i<=high;i++){
    int64_t res=ds.query(m,i);
    if(res>=max){
      maxi=i;
      max=res;
    }
  }
  best=std::max(best,max);
  //printf("best with l=%ld: %ld\n",m,max);
  solve(l,m,low,maxi);
  solve(m,r,maxi,high);
}

int64_t brute(int64_t l,int64_t r){
  if(r-l+1<M) return -INF;
  std::multiset<int> best;
  for(int64_t i=l+1;i<r;i++){
    best.insert(cake[i].second);
  }
  while(best.size()>M-2){
    best.erase(best.begin());
  }
  assert(best.size()==M-2);
  best.insert(cake[l].second);
  best.insert(cake[r].second);
  int64_t sum=2LL*(cake[l].first-cake[r].first);
  for(int64_t x:best){
    sum+=x;
  }
  return sum;
}

int main(){
  scanf("%ld %ld",&N,&M);
  for(int64_t i=0;i<N;i++){
    int64_t V,C;
    scanf("%ld %ld",&V,&C);
    cake.push_back({C,V});
  }
  std::sort(cake.begin(),cake.end());
  /*
    for(int64_t l=0;l<N;l++){
    for(int64_t r=0;r<N;r++){
    printf("%ld,%ld ",ds.query(l,r),brute(l,r));
    }
    printf("\n");
    }
  */
  solve(-1,N,0,N-1);
  /*
  for(int64_t l=0;l<N;l++){
    for(int64_t r=l;r<N;r++){
      best=std::max(best,brute(l,r));
    }
  }
  */
  printf("%ld\n",best);
  //ds.query(0,N-1),ds.dump();
  return 0;
}

Compilation message (stderr)

cake3.cpp: In member function 'void DataStruct::balance()':
cake3.cpp:32:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(low.size()&&high.size()<M-2){
                       ~~~~~~~~~~~^~~~
cake3.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(high.size()>M-2){
           ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from cake3.cpp:5:
cake3.cpp: In member function 'int64_t DataStruct::query(int64_t, int64_t)':
cake3.cpp:64:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(high.size()+low.size()==r-l-1);
            ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
cake3.cpp: In function 'int64_t brute(int64_t, int64_t)':
cake3.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(best.size()>M-2){
         ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from cake3.cpp:5:
cake3.cpp:105:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(best.size()==M-2);
          ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%ld %ld",&N,&M);
   ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%ld %ld",&V,&C);
     ~~~~~^~~~~~~~~~~~~~~~~

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