Submission #195622

#	Time	Username	Problem	Language	Result	Execution time	Memory
195622		jovan_b	Rice Hub (IOI11_ricehub)	C++17	100 / 100	22 ms	2552 KiB

ricehub

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

using namespace std;

typedef long long ll;

ll niz[100000];
ll mani;
int N;

bool moze(int x){
    ll trencost=0;
    int trenmid, r=x, l=1;
    trenmid = (x+2)/2;
    for(int i=1; i<=x; i++){
        trencost += abs(niz[i]-niz[trenmid]);
    }
    if(trencost <= mani) return true;
    while(r < N){
        r++;
        trenmid++;
        trencost -= niz[trenmid-1]-niz[l];
        trencost += niz[r]-niz[trenmid];
        l++;
        trencost += (niz[trenmid]-niz[trenmid-1])*(trenmid-l);
        trencost -= (niz[trenmid]-niz[trenmid-1])*(r-trenmid);
        if(trencost <= mani) return true;
    }
    return false;
}

int besthub(int n, int L, int X[], long long B){
    N = n;
    mani = B;
    for(int i=1; i<=n; i++){
        niz[i] = X[i-1];
    }
    int l=1, r=n;
    int maxres=1;
    while(l <= r){
        int mid = (l+r)/2;
        if(moze(mid)){
            l = mid+1;
            maxres = max(maxres, mid);
        }
        else r = mid-1;
    }
    return maxres;
}

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