Submission #1236712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236712		fauntleroy	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	1864 KiB

ricehub

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
//#include "ricehub.h"
#define ll long long
using namespace std;

int besthub(int R, int L, int X[], ll B) {
    int n = R;
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; ++i)
        pref[i + 1] = pref[i] + X[i];
    vector<int>x(n);
    for (int i = 0; i < n; ++i)
        x[i] = X[i];

    int l = 1, r = n;
    int ans = 0;
    while (l <= r) {
        int k = (l + r) >> 1;
        bool f = 0;
        for (int i = 0; i <= n - k; ++i) {
            int l1 = i, r1 = i + k - 1;
            int pos = x[l1 + k / 2];
            int id = lower_bound(x.begin() + l1, x.begin()+r1+1, pos) - x.begin();
            int cl = id - l1;
            int cr = r1 - id;
            ll ls = pref[id] - pref[l1];
            ll rs = pref[r1 + 1] - pref[id + 1];
            ll d = (ll)pos * cl - ls + rs - (ll)pos * cr;
            if (d <= B) {
                f = 1;
                break;
            }
        }
        //cout << l1<<' '<<r1<<' '<<pos << ' ' << d << ' ' << k << '\n';
        
        if (!f) 
            r = k - 1;
        else
            l = k + 1, ans = max(ans, k);
    }
    return ans;
}

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