Submission #434105

#	Time	Username	Problem	Language	Result	Execution time	Memory
434105		illyakr	Rice Hub (IOI11_ricehub)	C++14	68 / 100	443 ms	1476 KiB

ricehub

#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 tr(ll x) {
    ll now = have;
    ll cl = 1;
    for (ll i = 1; i <= n; i++) {
        if (Abs(a[i] - x) < Abs(a[cl] - x))
            cl = i;
    }
    ll ans = 0;

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


            if (l >= 1 && r <= n && Abs(a[l] - x) <= Abs(a[r] - x) && Abs(a[l] - x) <= now) {
                now -= Abs(a[l] - x);
                l--;ans++;continue;
            }
            if (l >= 1 && 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 (ll i = 0; i < R; i++)
        a[i + 1] = X[i];
    have = B;

    int l = 0, r = L + 1;
    while (l + 1000 < r) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if (tr(m1) <= tr(m2))
            l = m1;
        else
            r = m2;
    }
    for (ll i = l; i <= r; i++) {
        ans = max(ans, tr(i));
    }
    return ans;
}

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

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32