Submission #146935

#	Time	Username	Problem	Language	Result	Execution time	Memory
146935		karma	Rice Hub (IOI11_ricehub)	C++11	100 / 100	39 ms	3320 KiB

ricehub

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

using namespace std;

const int N = int(1e5) + 7;

ll sum[N], pos[N];

ll Cost(int l, int r)
{
    int mid = (l + r) >> 1;
    ll res = (ll)1e18, cost;
    for(int i = max(mid - 1, l); i <= min(mid + 1, r); ++i) {
        cost = 1ll * (i - l + 1) * pos[i] - (sum[i] - sum[l - 1]);
        cost += sum[r] - sum[i] - 1ll * (r - i) * pos[i];
        res = min(res, cost);
    }
    return res;
}

int besthub(int n, int l, int x[], ll b)
{
    int res = 0, lef, rig, mid;
    for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (pos[i] = x[i - 1]);
    for(int i = 1; i <= n; ++i) {
        lef = 1, rig = i;
        while(lef <= rig) {
            mid = (lef + rig) >> 1;
            if(Cost(mid, i) > b) lef = mid + 1;
            else rig = mid - 1;
        }
        res = max(res, i - lef + 1);
    }
    return res;
}

/*int _n, _l, _x[N], _b;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
      freopen("test.inp", "r", stdin);
      freopen("test.out", "w", stdout);
    }

    cin >> _n >> _l;
    for(int i = 0; i < _n; ++i) cin >> _x[i];
    cin >> _b;
    cout << besthub(_n, _l, _x, _b);

    return 0;
}*/

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