Submission #49758

#	Time	Username	Problem	Language	Result	Execution time	Memory
49758		gs13105	Rice Hub (IOI11_ricehub)	C++17	100 / 100	293 ms	3384 KiB

ricehub

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

const int MAXR = 100000;

int pos[MAXR + 10];
int cnt[MAXR + 10];
int csum[MAXR + 10];
long long bsum[MAXR + 10];
int m = 1;

int besthub(int R, int L, int X[], long long B)
{
    for(int i = 0; i < R; i++)
    {
        if(i && X[i] != X[i - 1])
            m++;
        pos[m] = X[i];
        cnt[m]++;
    }

    for(int i = 1; i <= m; i++)
        csum[i] = csum[i - 1] + cnt[i];

    for(int i = 1; i <= m; i++)
        bsum[i] = bsum[i - 1] + 1LL * cnt[i] * pos[i];

    int res = 0;
    for(int i = 1; i <= m; i++)
    {
        int s = 0;
        int g = max(L - i, i - 1);
        while(s < g)
        {
            int x = (s + g + 1) / 2;
            int l = lower_bound(pos + 1, pos + m + 1, pos[i] - x) - pos;
            int r = upper_bound(pos + 1, pos + m + 1, pos[i] + x) - pos - 1;

            long long ls = (l == i) ? 0 : 1LL * pos[i] * (csum[i] - csum[l - 1]) - (bsum[i] - bsum[l - 1]);
            long long rs = (r == i) ? 0 : (bsum[r] - bsum[i - 1]) - 1LL * pos[i] * (csum[r] - csum[i - 1]);
            long long t = ls + rs;

            if(pos[i] - pos[l] == pos[r] - pos[i])
                t -= 1LL * (pos[i] - pos[l]) * (cnt[l] + cnt[r] - 1);
            else if(pos[i] - pos[l] > pos[r] - pos[i])
                t -= 1LL * (pos[i] - pos[l]) * (cnt[l] - 1);
            else
                t -= 1LL * (pos[r] - pos[i]) * (cnt[r] - 1);

            if(t <= B)
                s = x;
            else
                g = x - 1;
        }
        int l = lower_bound(pos + 1, pos + m + 1, pos[i] - s) - pos;
        int r = upper_bound(pos + 1, pos + m + 1, pos[i] + s) - pos - 1;

        long long ls = (l == i) ? 0 : 1LL * pos[i] * (csum[i] - csum[l - 1]) - (bsum[i] - bsum[l - 1]);
        long long rs = (r == i) ? 0 : (bsum[r] - bsum[i - 1]) - 1LL * pos[i] * (csum[r] - csum[i - 1]);
        long long t = ls + rs;
        int c = csum[r] - csum[l - 1];

        if(t > B)
        {
            int mx = max(pos[i] - pos[l], pos[r] - pos[i]);
            c -= (t - B + mx - 1) / mx;
        }

        res = max(res, c);
    }

    return res;
}

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