Submission #410118

#	Time	Username	Problem	Language	Result	Execution time	Memory
410118		Leonardo_Paes	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	2920 KiB

ricehub

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

typedef long long ll;

const int maxn = 1e5+10;

ll sum[maxn];

bool check(int n, int l, const vector<int> &v, ll b, int k){
    for(int i=k-1; i<n; i++){
        int j = i - k + 1;
        int meio = (i + j) >> 1;
        ll val = sum[i] - sum[meio] - v[meio] * (i-meio);
        val += -sum[meio] + (j == 0 ? 0 : sum[j-1]) + v[meio] * (meio - j + 1);
        if(val <= b) return true;
    }
    return false;
}

int besthub(int n, int l, int x[], ll b){
	vector<int> v(n);
	for(int i=0; i<n; i++) v[i] = x[i];   
    sum[0] = v[0];
    for(int i=1; i<n; i++) sum[i] = v[i] + sum[i-1];
    int ini = 1, meio, fim = n, ans = 1;
    while(ini <= fim){
        meio = (ini + fim) >> 1;
        if(check(n, l, v, b, meio)){
            ans = meio;
            ini = meio + 1;
        }
        else fim = meio - 1;
    }
    return ans;
}

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