Submission #453667

#	Time	Username	Problem	Language	Result	Execution time	Memory
453667		ponytail	Rice Hub (IOI11_ricehub)	C++17	100 / 100	22 ms	3276 KiB

ricehub

#include "ricehub.h"
#include "bits/stdc++.h"
#define int long long
using namespace std;
signed besthub(signed R, signed L, signed X[], int B){
    int N = R;
    int x[N+1], ps[N+1], ans=0, lb=1, rb=N;
    for(int i=1;i<=N;i++)x[i] = X[i-1];
    ps[0]=0;
    for(int i=1;i<=N;i++) ps[i]=ps[i-1]+x[i];
    while(lb<rb){
        int mid=(lb+rb+1)/2;
        bool ok=0;
        for(int i=1;i<=N-mid+1;i++){
            int idx=(2*i+mid-1)/2;
            int cost=x[idx]*(idx-i+1)-ps[idx]+ps[i-1]+ps[i+mid-1]-ps[idx-1]-x[idx]*(i+mid-idx);
            if(cost<=B) ok=1;
        }
        if(ok) lb=mid;
        else rb=mid-1;
    }
    return lb;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:7:26: warning: unused variable 'ans' [-Wunused-variable]
    7 |     int x[N+1], ps[N+1], ans=0, lb=1, rb=N;
      |                          ^~~

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