Submission #869858

#	Time	Username	Problem	Language	Result	Execution time	Memory
869858		Namviet2704	Rice Hub (IOI11_ricehub)	C++17	100 / 100	12 ms	4132 KiB

ricehub

// #include "ricehub.h"

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 2;

/// You can declare global variables here if necessary.
/// But you are NOT allowed to write main function.

vector<int> a;
ll dis[N];
int r, l;
ll money;

bool check(int num)
{
    for (int i = 1; i <= (r - num + 1); i++)
    {
        int j = i + num - 1;
        int mid = (j + i) / 2;
        ll ans = (dis[j] - dis[mid] - 1ll * a[mid] * (j - mid)) + (1ll * a[mid] * (mid - i + 1) - (dis[mid] - dis[i - 1]));
        // cout << i << " " << j << " " << mid << " " << ans << '\n';
        if (ans <= money)
            return true;
    }
    return false;
}

/// You have to implement the below functions:
int besthub(int g, int h, int x[], ll b)
{
    r = g;
    a.push_back(0);
    for (int i = 0; i < r; i++)
        a.push_back(x[i]);
    for (int i = 1; i <= r; i++)
        dis[i] = dis[i - 1] + a[i];
    money = b;
    int low = 1, high = r, mid, ans = -1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (check(mid))
        {
            ans = mid;
            low = mid + 1;
        }
        else
            high = mid - 1;
    }
    return ans;
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> r >> l;
    vector<int> tmp;
    for (int i = 1; i <= r; i++)
    {
        int x;
        cin >> x;
        tmp.push_back(x);
    }
    cin >> money;
    cout << besthub(r, l, tmp, money);
    return 0;
}
*/

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