Submission #1254172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254172		asim	Rice Hub (IOI11_ricehub)	C++20	68 / 100	1087 ms	1352 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;

bool check(long long m, long long n, long long b, const vector<long long> &arr)
{
    if (m > n)
    {
        return false;
    }
    for (int i = 1; i <= n - m + 1; i++)
    {
        long long a = 0;
        for (int j = i; j < i + m; j++)
        {
            a += (abs(arr[j] - arr[i + m / 2]));
        }
        if (a <= b)
        {
            return true;
        }
    }
    return false;
}

int besthub(int n, int r, int *input_array, long long b)
{
    vector<long long> arr(n + 10);
    for (int i = 1; i <= n; i++)
    {
        arr[i] = input_array[i - 1];
    }
    long long l1 = 1;
    long long best = 1;
    while (l1 <= r)
    {
        long long m = (r + l1) / 2;
        if (check(m, n, b, arr))
        {
            l1 = m + 1;
            best = m;
        }
        else
        {
            r = m - 1;
        }
    }
    return best;
}

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