Submission #1013841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013841		Muhammet	Rice Hub (IOI11_ricehub)	C++17	100 / 100	12 ms	2520 KiB

ricehub

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

#define sz(s) (int)s.size()

using namespace std;

#define ll long long 

vector <int> v;

bool f(int x, ll b, int n){
    ll k = 0, ind = x/2, in = x-1;
    for(int i = 0; i < in; i++){
        k += abs(v[ind]-v[i]);
    }
    while(in < n){
        k += abs(v[in]-v[ind]);
        if(k <= b) return true;
        k -= (in-ind)*(v[ind+1]-v[ind]);
        k += (ind-(in-x+1))*(v[ind+1]-v[ind]);
        k -= (v[ind]-v[in-x+1]);
        in++;
        ind++;
    }
    return false;
}

int besthub(int n, int L, int a[], ll b){
    for(int i = 0; i < n; i++) v.push_back(a[i]);
    int l = 2, r = n, ans = 1;
    while(l <= r){
        int md = (l + r) / 2;
        if(f(md,b,n) == 1){
            l = md+1;
            ans = md;
        }
        else {
            r = md-1;
        }
    }
    return ans;
}

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