Submission #1110450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110450		Icelast	Rice Hub (IOI11_ricehub)	C++17	100 / 100	14 ms	5372 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;

int besthub(int R, int L, int X[], long long B)
{
    int n = R;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        a[i] = X[i-1];
    }
    vector<ll> pf(n+2, 0);
    for(int i = 1; i <= n; i++){
        pf[i] = pf[i-1]+a[i];
    }
    auto check = [&](int x) -> bool{
        for(int i = x; i <= n; i++){
            int j = i-x+1;
            int m = j+(x+1)/2-1;
            ll left_cost = a[m]*(m-j+1) - (pf[m]-pf[j-1]);
            ll right_cost = (pf[i]-pf[m]) - a[m]*(i-m);
            ll cost = left_cost+right_cost;
            if(cost <= B) return true;
        }
        return false;
    };
    int l = 0, r = n, mid;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)){
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return l-1;
}

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