oj.uz

Submission #434155

# Submission time Handle Problem Language Result Execution time Memory
434155 2021-06-20T15:57:33 Z illyakr Rice Hub (IOI11_ricehub) C++14
68 / 100
 123 ms 2252 KB 
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

ll Abs(ll x) {
    if (x < 0)return -x;
    return x;
}

ll have;
ll n;
ll a[101010];
ll res = 0;
ll pref[101010];
ll gt(ll l, ll r) {
    return pref[r] - pref[l - 1];
}
ll scbp(ll sum, ll id) {
    ll l = 0, r = id + 1;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        int md = (a[id] * (id - mid + 1)) - gt(mid, id);
        if (md + sum > have)l = mid;
        else r = mid;
    }
    return r;
}

int besthub(int R, int L, int X[], long long B) {
    n = R;
    for (ll i = 0; i < R; i++)
        a[i + 1] = X[i];
    have = B;
    for (ll i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }

    int sumL = 0, sumR = 0;
    for (int i = 1; i <= n; i++)sumR += a[i];

    for (int i = 1; i <= n; i++) {
        int l = i - 1, r = n + 1;
        while (l + 1 <= r) {
            if (l + 1 == r)break;
            ll mid = (l + r) / 2;
            ll cnt = gt(i, mid) - (a[i] * (mid - i + 1));
            if (cnt > have){r = mid;continue;}
            ll id = scbp(cnt, i);
            res = max(res, mid - id + 1);

            if (id == 1){l = mid;continue;}
            if (abs(a[id - 1] - a[i]) < abs(a[mid] - a[i])){r = mid;continue;}
            l = mid;
        }
    }

    return res;
}

/**
5 20 6
1
2
10
12
14
3
*/

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:39:9: warning: unused variable 'sumL' [-Wunused-variable]
   39 |     int sumL = 0, sumR = 0;
      |         ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 252 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 1 ms 296 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 680 KB Output is correct
2 Correct 11 ms 696 KB Output is correct
3 Correct 123 ms 2252 KB Output is correct
4 Incorrect 92 ms 2252 KB Output isn't correct
5 Halted 0 ms 0 KB -