Submission #237071

#	Time	Username	Problem	Language	Result	Execution time	Memory
237071		nicolaalexandra	Rice Hub (IOI11_ricehub)	C++14	100 / 100	24 ms	2944 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
#define DIM 200010
using namespace std;

long long sp[DIM];
int v[DIM];

long long get_sum (int x, int y){
    if (x > y)
        return 0;

    return sp[y] - sp[x-1];
}

int verif (int val, int n, long long b){

    for (int i=1;i<=n-val+1;i++){
        int st = i, dr = i + val-1;
        int mid = (st + dr)>>1; /// aici fixez locatia

        long long dist = 1LL * (mid-st) * v[mid] - get_sum (st,mid-1);
        dist += get_sum (mid+1,dr) - 1LL * (dr - mid) * v[mid];

        if (dist <= b)
            return 1;

    }
    return 0;

}

int besthub (int n, int l, int x[], long long b){

    for (int i=0;i<n;i++){
        v[i+1] = x[i];
        sp[i+1] = sp[i] + v[i+1];
    }

    int st = 1, dr = n, sol = 1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid,n,b)){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;
    }

    return sol;
}

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