Submission #56498

#	Time	Username	Problem	Language	Result	Execution time	Memory
56498		Bodo171	Rice Hub (IOI11_ricehub)	C++14	100 / 100	31 ms	17032 KiB

ricehub

#include "ricehub.h"
#include <iostream>
const int nmax=100005;
long long v[nmax],sum[nmax];
int i,p,mx;
long long S(int l,int r)
{
    return sum[r]-sum[l-1];
}
long long cost(int st,int dr)
{
    int poz=(st+dr)/2;
    return (1LL*(poz-st+1)*v[poz]-S(st,poz)+S(poz+1,dr)-1LL*(dr-poz)*v[poz]);
}
int besthub(int R, int L, int X[], long long B)
{
  for(i=1;i<=R;i++)
    sum[i]=X[i-1]+sum[i-1],v[i]=X[i-1];
  p=1;
  for(i=1;i<=R;i++)
  {
      while(cost(p,i)>B)
        p++;
      if(i-p+1>mx)
        mx=i-p+1;
  }
  return mx;
}

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