Submission #172988

#	Time	Username	Problem	Language	Result	Execution time	Memory
172988		FieryPhoenix	Rice Hub (IOI11_ricehub)	C++11	100 / 100	32 ms	2680 KiB

ricehub

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int besthub(int R, int L, int x[], ll B){
  ll X[R+1];
  int ans=1;
  for (int i=1;i<=R;i++)
    X[i]=x[i-1];
  int r=1,mid=1;
  ll cost=0;
  for (int i=1;i<=R;i++){
    while (r<=R && cost<=B){
      r++;
      if (r>R)
	break;
      int newMid=(i+r)/2;
      //cout<<mid<<' '<<newMid<<endl;
      if (newMid==mid)
	cost+=X[r]-X[mid];
      else{
        ll diff=X[newMid]-X[mid];
	cost+=(mid-i+1)*diff;
	cost-=(r-1-newMid+1)*diff;
	cost+=X[r]-X[newMid];
	mid=newMid;
      }
    }
    ans=max(ans,r-i);
    //cout<<"RANGE "<<i<<' '<<r<<" cost "<<cost<<endl;
    int newMid=(i+1+r)/2;
    //cout<<mid<<' '<<newMid<<endl;
    if (newMid==mid)
      cost-=(X[mid]-X[i]);
    else{
      ll diff=X[newMid]-X[mid];
      cost+=(mid-(i+1)+1)*diff;
      cost-=(min(r,R)-newMid+1)*diff;
      cost-=(X[mid]-X[i]);
      mid=newMid;
    }
  }
  return ans;
}

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