Submission #100445

#	Time	Username	Problem	Language	Result	Execution time	Memory
100445		alexpetrescu	Rice Hub (IOI11_ricehub)	C++14	100 / 100	305 ms	2680 KiB

ricehub

#include "ricehub.h"
#include <algorithm>

#define MAXN 100000

int cnt;
long long sum[MAXN + 1];

inline long long f(int p, int k, int n, int X[]) {
    int rez = p;
    for (int pas = 1 << 16; pas; pas >>= 1)
        if (rez + pas <= n && X[rez + pas] <= X[p] + k)
            rez += pas;
    long long ans = sum[rez] - sum[p - 1] - 1LL * (rez - p + 1) * X[p];
    cnt = rez - p + 1;
    rez = p;
    for (int pas = 1 << 16; pas; pas >>= 1)
        if (rez - pas > 0 && X[rez - pas] >= X[p] - k)
            rez -= pas;
    cnt += p - rez;
    ans += 1LL * (p - rez) * X[p] - (sum[p - 1] - sum[rez - 1]);
    return ans;
}

inline int solve(int p, long long B, int n, int X[]) {
    int rez = -1, cati = 0;
    for (int pas = 1 << 29; pas; pas >>= 1)
        if (f(p, rez + pas, n, X) <= B)
            rez += pas, cati = cnt;
    if (cati == n)
        return cati;
    return cati + (B - f(p, rez, n, X)) / (rez + 1);
}

int besthub(int R, int L, int X[], long long B) {
    for (int i = R; i > 0; i--)
        X[i] = X[i - 1];
    for (int i = 1; i <= R; i++)
        sum[i] = sum[i - 1] + X[i];
    int ans = 0;
    for (int i = 1; i <= R; i++)
        ans = std::max(ans, solve(i, B, R, X));
    return ans;
}

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