Submission #1259978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259978		kawhiet	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	1096 KiB

ricehub

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

int besthub(int n, int m, int arr[], long long k) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = arr[i] - arr[0];
    }
    auto good = [&](int x) {
        int l = 0, r = x - 1, m = (l + r) / 2;
        long long cur = 0;
        for (int i = l; i <= r; i++) {
            cur += abs(a[i] - a[m]);
        }
        if (cur <= k) {
            return true;
        }
        while (r + 1 < n) {
            l++; r++; m++;
            cur = cur + (x % 2 == 0 ? 0 : (a[m] - a[m - 1])) + (a[r] - a[m]) - (a[m] - a[l - 1]);
            if (cur <= k) {
                return true;
            }
        }
        return false;
    };
    int l = 1, r = n + 1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (good(m)) {
            l = m;
        }
        else {
            r = m;
        }
    }
    return l;
}

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