Submission #805200

#	Time	Username	Problem	Language	Result	Execution time	Memory
805200		Kerim	Rice Hub (IOI11_ricehub)	C++17	100 / 100	11 ms	2256 KiB

ricehub

#include "ricehub.h"
#include "bits/stdc++.h"
#define ll long long

using namespace std;

bool check(int k, ll B, vector<int>&arr){
    ll cost = 0;
    int n = arr.size(), p = (k-1) / 2;
    for (int i = 0; i < k; i++)
        cost += abs(arr[i] - arr[p]);
    if (cost <= B)
        return true;
    for (int i = k; i < n; i++){
        int y = arr[i], x = arr[i - k];
        int m = arr[p], mp = arr[p+1];
        p += 1;
        if (k&1){
            cost += y + x;
            cost -= m + mp;
        }
        else{
            cost += y + x;
            cost -= mp + mp;
        }
        if (cost <= B)
            return true;
    }
    return false;
}
int besthub(int R, int L, int X[], long long B){
    vector<int> arr;
    for (int i = 0; i < R; i++)
        arr.push_back(X[i]);
    int st = 1, en = R;
    while (st < en){
        int mid = (st + en + 1) >> 1;
        if (check(mid, B, arr))
            st = mid;
        else    
            en = mid - 1;
    }
    return st;
}

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