Submission #114520

#	Time	Username	Problem	Language	Result	Execution time	Memory
114520		mosesmayer	Rice Hub (IOI11_ricehub)	C++17	100 / 100	22 ms	2660 KiB

ricehub

#include "ricehub.h"
#include <algorithm>

typedef long long LL;
LL all[100005];
int besthub(int R, int L, int X[], long long B)
{
  for (int i=1; i <= R; i++) all[i] = X[i-1];
  std::sort(all+1,all+R+1);
  LL left = 1, right = 1, mx = -1, totalSum = 0;
  LL median = 1, newmedian;
  LL cost = 0;
  LL mxInterval = -1;
  while (right <= R){
    totalSum += all[right];
    int range = (right-left+1);
    newmedian = (left+right)>>1;
    cost += all[right]-all[median];
    if (newmedian > median){
      while (median < newmedian){
        int change = median - left + 1 - (right - median);
        cost += 1LL * change * (all[median+1]-all[median]);
        median++;
      }
    }
    while (cost > B){
      left++;
      cost -= all[median] - all[left-1];
      while (median < ((left+right)>>1)){
        int change = median - left + 1 - (right - median);
        cost += 1LL * change * (all[median+1]-all[median]);
        median++;
      }
    }
    mxInterval = std::max(mxInterval, right - left + 1);
    right++;
  }
  return mxInterval;

  //return R;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:16:9: warning: unused variable 'range' [-Wunused-variable]
     int range = (right-left+1);
         ^~~~~
ricehub.cpp:10:27: warning: unused variable 'mx' [-Wunused-variable]
   LL left = 1, right = 1, mx = -1, totalSum = 0;
                           ^~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32