oj.uz

Submission #956962

# Submission time Handle Problem Language Result Execution time Memory
956962 2024-04-02T18:06:47 Z Nelt Rice Hub (IOI11_ricehub) C++17
0 / 100
 2 ms 604 KB 
#include "ricehub.h"
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
using namespace std;

int besthub(int n, int L, int x[], long long B)
{
    ll ans = 0, pref[n];
    for (ll i = 0; i < n; i++)
        pref[i] = (i - 1 >= 0 ? pref[i - 1] : 0) + x[i];
    auto sum = [&](ll l, ll r)
    {
        return pref[r] - (l - 1 >= 0 ? pref[l - 1] : 0);
    };
    auto best = [&](ll l, ll r)
    {
        ll lo = l, hi = r - 1, mid, ans = x[r] * (r - l + 1) - sum(l, r);
        while (lo <= hi)
        {
            mid = (lo + hi) >> 1;
            ans = min({ans, x[mid] * (mid - l + 1) - x[mid] * (r - mid) + sum(mid + 1, r) - sum(l, mid), x[mid + 1] * (mid + 1 - l + 1) - x[mid + 1] * (r - (mid + 1)) + sum(mid + 2, r) - sum(l, mid + 1)});
            if (x[mid] * (mid - l + 1) - x[mid] * (r - mid) + sum(mid + 1, r) - sum(l, mid) < x[mid + 1] * (mid + 1 - l + 1) - x[mid + 1] * (r - (mid + 1)) + sum(mid + 2, r) - sum(l, mid + 1))
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return ans;
    };
    for (ll i = 0, j = 0; i < n; i++)
    {
        while (best(i, j) > B)
            j++;
        ans = max(ans, i - j + 1);
    }
    return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -