oj.uz

Submission #869858

# Submission time Handle Problem Language Result Execution time Memory
869858 2023-11-06T02:33:41 Z Namviet2704 Rice Hub (IOI11_ricehub) C++17
100 / 100
 12 ms 4132 KB 
// #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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2496 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2496 KB Output is correct
15 Correct 0 ms 2648 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2392 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2492 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2496 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2504 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2508 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2520 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2392 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2908 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 10 ms 4056 KB Output is correct
4 Correct 12 ms 4056 KB Output is correct
5 Correct 6 ms 3148 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 8 ms 3800 KB Output is correct
8 Correct 8 ms 3752 KB Output is correct
9 Correct 5 ms 3288 KB Output is correct
10 Correct 5 ms 3236 KB Output is correct
11 Correct 10 ms 4056 KB Output is correct
12 Correct 10 ms 4056 KB Output is correct
13 Correct 6 ms 3236 KB Output is correct
14 Correct 6 ms 3288 KB Output is correct
15 Correct 11 ms 4012 KB Output is correct
16 Correct 7 ms 3800 KB Output is correct
17 Correct 9 ms 4008 KB Output is correct
18 Correct 9 ms 4056 KB Output is correct
19 Correct 9 ms 4056 KB Output is correct
20 Correct 9 ms 4132 KB Output is correct