Submission #348693

#	Time	Username	Problem	Language	Result	Execution time	Memory
348693		idk321	Rice Hub (IOI11_ricehub)	C++11	100 / 100	22 ms	1132 KiB

ricehub

    #include "ricehub.h"

    #include <bits/stdc++.h>

    using namespace std;

    typedef long long ll;

    const int N = 100005;
    int pos[N];

    int n;
    long long money;

    bool poss(int len)
    {
        ll cost = 0;
        int a = 0;
        int b = len - 1;
        int mid = (a + b) / 2;
        int left = 0;
        int right = 0;
        for (int i = a; i <= b; i++)
        {
            cost += abs(pos[i] - pos[mid]);
        }
        left = mid - a;
        right = b - mid;
        //cout << len << " " << cost << " " << money << endl;
        if (cost <= money) return true;
        while (b + 1 < n)
        {
            cost -= pos[mid] - pos[a];
            cost += ((ll)left) * (pos[mid + 1] - pos[mid]);
            cost -= ((ll)right) * (pos[mid + 1] - pos[mid]);
            mid++;
            a++;
            b++;
            cost += pos[b] - pos[mid];
            if (cost <= money) return true;
        }

        return false;
    }

    int binarySearch()
    {
        int a = 1;
        int b = n;
        int res = -1;
        while (a <= b)
        {
            int mid = (a + b) / 2;
            if (poss(mid))
            {
                res = mid;
                a = mid + 1;
            } else
            {
                b = mid - 1;
            }
        }

        return res;
    }

    int besthub(int n1, int l, int x[], long long money1)
    {
        money = money1;
        n = n1;
        for (int i = 0; i < n; i++)
        {
            pos[i] = x[i];
        }

      return binarySearch();
    }

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