Submission #494564

#	Time	Username	Problem	Language	Result	Execution time	Memory
494564		Alexandruabcde	Rice Hub (IOI11_ricehub)	C++14	100 / 100	18 ms	2764 KiB

ricehub

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

using namespace std;

typedef long long LL;
constexpr int NMAX = 1e5 + 5;

int N;
int LgMax;

LL sp[NMAX];
int V[NMAX];
LL Budget;

LL Sum (int st, int dr, int j) {
    LL ans = sp[dr] + sp[st-1] - 2 * sp[j];
    LL semn = (2 * j + 2 - 2 * st - (dr - st + 1));

    if (semn < 0) return ans + 1LL * (V[j+1]-1) * semn;

    return ans + 1LL * V[j] * semn;
}

bool BruteCheck (int K) {
    for (int l = 1; l <= N - K + 1; ++ l ) {
        int r = l + K - 1;
        int j = l;
        for (int P = V[l]; P <= V[r]; ++ P ) {
            while (j <= r && V[j] <= P) ++ j;
            -- j;

            LL val = P * (2 * j + 2 - 2 * l - K) - 2 * sp[j] + sp[l-1] + sp[r];

            if (val <= Budget)
            {
                cout << l << " " << r << " " << P << '\n';
                return 1;
            }
        }
    }

    return 0;
}

bool Check (int K) {
    int j = 1;

    while (j < K && Sum(1, K, j) > Sum(1, K, j+1)) ++ j;

    if (Sum(1, K, j) <= Budget) return 1;

    for (int l = 2; l <= N - K + 1; ++ l ) {
        int r = l + K - 1;

        while (j < r && Sum(l, r, j) > Sum(l, r, j+1)) ++ j;

        LL Min = Sum(l, r, j);

        if (Min <= Budget) return 1;
    }

    return 0;
}

int besthub(int R, int L, int X[], long long B)
{
    N = R, LgMax = L;
    for (int i = 1; i <= N; ++ i )
        V[i] = X[i-1];
    for (int i = 1; i <= N; ++ i )
        sp[i] = sp[i-1] + 1LL * V[i];

    Budget = B;

    int st = 1, dr = N;
    int ans = 1;
    while (st <= dr) {
        int mij = (st + dr) >> 1;

        if (Check(mij)) {
            ans = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    return ans;
}

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