Submission #17007

#	Time	Username	Problem	Language	Result	Execution time	Memory
17007		erdemkiraz	Rice Hub (IOI11_ricehub)	C++98	100 / 100	24 ms	6800 KiB

ricehub

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

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e5 + 5;

int n;
int a[N];
ll m;
ll L[N];

int ptr, ans = 1;

ll getL(int i, int j) {
    return (ll) (j - i + 1) * a[j] - (L[j] - L[i - 1]);
}

ll getR(int i, int j) {
    return L[j] - L[i - 1] - (ll) (j - i + 1) * a[i];
}

bool check(int i, int j) {
    int mid = i + j >> 1;
    return getL(i, mid) + getR(mid, j) <= m;
}

void solve() {
    for(int i = 1; i <= n; i++)
        L[i] = L[i - 1] + a[i];
    int ptr = 1;
    for(int i = 1; i <= n; i++) {
        ptr = max(ptr, i);
        while(ptr + 1 <= n and check(i, ptr + 1))
            ptr++;
        ans = max(ans, ptr - i + 1);
    }
}

int besthub(int R, int L, int X[], long long B) {
    n = R;
    m = B;
    for(int i = 0; i < n; i++) {
        a[i + 1] = X[i];
    }
    solve();
    return ans;
}

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