oj.uz

Submission #434153

# Submission time Handle Problem Language Result Execution time Memory
434153 2021-06-20T15:55:53 Z illyakr Rice Hub (IOI11_ricehub) C++14
0 / 100
 103 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;
    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, 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);

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

    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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.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 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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