Submission #235565

#	Time	Username	Problem	Language	Result	Execution time	Memory
235565		Toirov_Sadi	Rice Hub (IOI11_ricehub)	C++17	100 / 100	26 ms	2560 KiB

ricehub

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

using namespace std;

int besthub(int n, int L, int X[], long long B){

    vector<long long> p(n, 0);
    for(int i = 0; i < n; i ++){
        if(i > 0) p[i] = p[i - 1];
        p[i] += X[i];
    }
    int l = 0, r = n;
    while(l < r){
        int m = ((l + r) / 2) + 1;

        /// can m ?
        bool can = false;
        for(int i = 0; i + m < n; i ++){
            int l1 = i, r1 = i + m;
            int mid = (l1 + r1) / 2;
            int x = (m + 2) / 2;
            int y = (m + 1) - ((m + 2) / 2);
            long long cur = x * 1ll * X[mid] - (p[mid] - (l1 == 0 ? 0 : p[l1 - 1]));
            cur += (p[r1] - p[mid]) - y * 1ll * X[mid];
            if(cur <= B) can = true;
        }

        if(can == true){
            l = m;
        }
        else{
            r = m - 1;
        }
    }
    return l + 1;
}

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