Submission #875016

#	Time	Username	Problem	Language	Result	Execution time	Memory
875016		StefanL2005	Rice Hub (IOI11_ricehub)	C++14	100 / 100	17 ms	4700 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long


int besthub(int R, int L, int X[], ll B)
{
    int ans = 1;
    vector<ll> Sum(R, 0);

    for (int i = 1; i < R; i++)
        Sum[i] = Sum[i - 1] + X[i] - X[0];

    for (int i = 0; i < R; i++)
    {
        int c1 = i, c2 = R - 1;

        while (c1 <= c2)
        {
            int m = (c1 + c2) / 2;
            int hub = (i + m) / 2;

            ll S = 0;
            S += 1LL * (X[hub] - X[i]) * (hub - i + 1) - (Sum[hub] - Sum[i] - 1LL * (hub - i) * (X[i] - X[0]));
            S += Sum[m] - Sum[hub] - 1LL * (m - hub) * (X[hub] - X[0]);

            if (S <= B)
            {
                ans = max(ans, m - i + 1);
                c1 = m + 1;
            }
            else
                c2 = m - 1;
        }
    }  
    
    return ans;
}

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