Submission #1263077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263077		sohamsen15	Rice Hub (IOI11_ricehub)	C++20	100 / 100	12 ms	1864 KiB

ricehub

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

int besthub(int n, int maxCoordinate, int aArr[], ll budget) {
    vector<int> a(n + 1); for (int i = 1; i <= n; i++) a[i] = aArr[i - 1]; int ans = 0;
    vector<ll> p(n + 1); p[0] = 0; for (int i = 1; i <= n; i++) p[i] = a[i] + p[i - 1];

    for (int l = 1, low = 1, high = n; l <= n; l++, low = l, high = n) 
        while (low <= high) 
            if (a[l + (((low + high) / 2) - l) / 2] * (2 * (l + (((low + high) / 2) - l) / 2) + 1 - l - ((low + high) / 2)) + (p[((low + high) / 2)] + p[l - 1] - 2 * p[l + (((low + high) / 2) - l) / 2]) <= budget) ans = max(ans, ((low + high) / 2) - l + 1), low = ((low + high) / 2) + 1;
            else high = ((low + high) / 2) - 1;

    return ans;
}

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