Submission #435315

#	Time	Username	Problem	Language	Result	Execution time	Memory
435315		alextodoran	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	326 ms	2628 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;
                }
                assert(l == r);

                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;
                }
                assert(l == r);

                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;
        if(e.first > budget)
            over = ((e.first - budget) + maxDist - 1) / maxDist;
        else
            over = 0;
        answer = max(answer, e.second - over);
    }
    return answer;
}

int brute (int n, int len, int pos[], ll budget)
{
    int answer = 0;
    for(int hub = 0; hub < n; hub++)
    {
        for(int l = 0; l <= hub; l++)
        {
            ll cost = 0;
            int cnt = 1;
            for(int i = hub - l; i < hub; i++)
            {
                cost += pos[hub] - pos[i];
                cnt++;
            }
            if(cost > budget)
                break;
            for(int i = hub + 1; i < n; i++)
            {
                cost += pos[i] - pos[hub];
                if(cost > budget)
                    break;
                cnt++;
            }
            answer = max(answer, cnt);
        }
    }
    return answer;
}

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