Submission #494560

#	Time	Username	Problem	Language	Result	Execution time	Memory
494560		Alexandruabcde	Rice Hub (IOI11_ricehub)	C++14	0 / 100	24 ms	2936 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 Check (int K) {
    int j = 1;
    LL Min = Sum(1, K, 1);
    LL val;

    for (; j <= K; ++ j )
        if ((val = Sum(1, K, j)) <= Min) Min = val;

    if (Min <= 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;

        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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32