Submission #1153022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153022		AlgorithmWarrior	Rice Hub (IOI11_ricehub)	C++20	100 / 100	17 ms	1864 KiB

ricehub

#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
#define MAX_R  1000000

static int R, L;
static long long B;
static int X[MAX_R];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

static void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %lld",&R,&L,&B));
  for(i=0; i<R; i++)
    my_assert(1==scanf("%d",&X[i]));
  my_assert(1==scanf("%d",&solution));
}

int v[MAX];
long long sp[MAX];
int r,l;
long long b;

void read()
{
    int i;
    for(i=1;i<=r;++i)
        sp[i]=v[i]+sp[i-1];
}

bool check(int ind,int nr)
{
    int half1=(nr+1)/2;
    long long used=1LL*half1*v[ind]-sp[ind]+sp[ind-half1];
    int half2=nr/2;
    used+=sp[ind+half2]-sp[ind]-1LL*half2*v[ind];
    return used<=b;
}

int bin_search(int ind)
{
    int left=1;
    int right=min(ind*2,(r-ind)*2+1)+1;
    while(right-left>1)
    {
        int mid=(left+right)/2;
        if(check(ind,mid))
            left=mid;
        else
            right=mid;
    }
    return left;
}

int find_answer()
{
    int i;
    int maxim=0;
    for(i=1;i<=r;++i)
        maxim=max(maxim,bin_search(i));
    return maxim;
}

int besthub(int R, int L, int X[], long long B){
  r=R;
  l=L;
  b=B;
  int i;
  for(i=1;i<=r;++i)
      v[i]=X[i-1];
  read();
  return find_answer();
}

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