oj.uz

Submission #434078

# Submission time Handle Problem Language Result Execution time Memory
434078 2021-06-20T14:45:58 Z illyakr Rice Hub (IOI11_ricehub) C++14
17 / 100
 1000 ms 588 KB 
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

ll have;
ll n;
ll a[101010];
ll tr(ll x) {
    ll now = have;
    int cl = 1;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        if (abs(a[i] - x) < abs(a[cl] - x))
            cl = i;
        sum += abs(a[i] - x);
    }
    ll ans = 0;
    ll cnt = now / sum;
    ans = cnt * n;
    now -= (cnt * sum);

    if (abs(a[cl] - x) <= now) {
        now -= abs(a[cl] - x);
        ans++;
        int l = cl - 1, r = cl + 1;
        while (true) {
            if (l < 1 && r > n)break;
            if (l < 1 && abs(a[r] - x) <= now) {
                now -= abs(a[r] - x);
                r++;ans++;continue;
            }
            if (r > n && abs(a[l] - x) <= now) {
                now -= abs(a[l] - x);
                l--;ans++;continue;
            }


            if (l >= 1 && abs(a[l] - x) < abs(a[r] - x) && abs(a[l] - x) <= now) {
                now -= abs(a[l] - x);
                l--;ans++;continue;
            }
            if (r <= n && abs(a[l] - x) >= abs(a[r] - x) && abs(a[r] - x) <= now) {
                now -= abs(a[r] - x);
                r++;ans++;continue;
            }

            break;
        }
    }
//    cout << x << " ---   " << ans << " " << cnt << endl;
    return ans;
}

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

    for (int i = 1; i <= L; i++) {
        ans = max(ans, tr(i));
    }
    return ans;
}

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

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 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
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 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 4 ms 252 KB Output is correct
3 Execution timed out 1083 ms 204 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 588 KB Time limit exceeded
2 Halted 0 ms 0 KB -