Submission #507161

#	Time	Username	Problem	Language	Result	Execution time	Memory
507161		amukkalir	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	2492 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std; 
typedef long long ll; 

const int nax = 1e5; 
ll p[nax+5]; 

ll cost(int  l, int r) {
  int m = (l+r)>>1; 
  ll d = p[m] - p[m-1]; 
  ll cnt = (r-l)+1; 
  //cout << " :: " << l << " " << r << endl; 
  //cout << (m-l)*d << " - " <<  p[m-1] <<" - " << p[l-1] <<" + " << p[r] << " - " << p[m] <<  " - " << d*(r-m) << " = " << (m-l)*d - p[m-1] + p[l-1] + p[r] - p[m] - d*(r-m) << endl;
  return (m-l)*d - p[m-1] + p[l-1] + p[r] - p[m] - d*(r-m); 
}

int besthub(int R, int L, int X[], long long B)
{ 
  for(int i=1; i<=R; i++) {
    p[i] = X[i-1] + p[i-1]; //make one based
    //cout << i << " " << p[i] << endl; 
  }

  int l = 1, r = 1; 
  int ans = 0; 
  while(l <= R && r <= R) {
    while(r+1 <= R && cost(l, r+1) <= B) {
      r++; 
      //cout << l << " " << r << endl; 
    }
    ans = max(ans, r-l+1); 
    l++; 
  }

  return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'll cost(int, int)':
ricehub.cpp:12:6: warning: unused variable 'cnt' [-Wunused-variable]
   12 |   ll cnt = (r-l)+1;
      |      ^~~

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