Submission #435294

#	Time	Username	Problem	Language	Result	Execution time	Memory
435294		alextodoran	Rice Hub (IOI11_ricehub)	C++17	17 / 100	186 ms	2480 KiB

ricehub

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

int besthub (int n, int len, int pos[], ll budget)
{
    ll sumPref[n];
    for(int i = 0; i < n; i++)
    {
        if(i >= 1)
            sumPref[i] = sumPref[i - 1];
        else
            sumPref[i] = 0;
        sumPref[i] += pos[i];
    }

    int answer = 0;
    for(int hub = 0; hub < n; hub++)
    {
        function <pair <ll, int> (int)> eval = [&] (int maxDist)
        {
            ll cost = 0;
            int cnt = 0;
            {
                int l = 0, r = hub;
                while(l < r)
                {
                    int mid = (l + r) / 2;
                    if(pos[hub] - pos[mid] <= maxDist)
                        r = mid;
                    else
                        l = mid + 1;
                }

                ll sumSeg = sumPref[hub];
                if(l >= 1)
                    sumSeg -= sumPref[l - 1];
                int cntSeg = (hub - l + 1);

                cost += 1LL * pos[hub] * cntSeg - sumSeg;
                cnt += cntSeg;
            }
            if(hub < n - 1)
            {
                int l = hub + 1, r = n - 1;
                while(l < r)
                {
                    int mid = (l + r + 1) / 2;
                    if(pos[mid] - pos[hub] <= maxDist)
                        l = mid;
                    else
                        r = mid - 1;
                }

                ll sumSeg = sumPref[r];
                sumSeg -= sumPref[hub];
                int cntSeg = (r - hub);

                cost += sumSeg - 1LL * pos[hub] * cntSeg;
                cnt += cntSeg;
            }
            return make_pair(cost, cnt);
        };

        int maxDist;
        {
            int l = 0, r = len;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                pair <ll, int> e = eval(mid);
                if(e.first <= budget)
                    l = mid;
                else
                    r = mid - 1;
            }
            assert(l == r);
            maxDist = l;
        }
        maxDist++;
        pair <ll, int> e = eval(maxDist);
        int over = ((e.first - budget) + maxDist - 1) / maxDist;
        answer = max(answer, e.second - over);
    }
    return answer;
}

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