Submission #1007747

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1007747	2024-06-25T12:33:47 Z	c2zi6	Rice Hub (IOI11_ricehub)	C++14	100 / 100	39 ms	4900 KB

ricehub

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "ricehub.h"

int n;
VI a;
VL pref;
ll B;
ll sum(int l, int r) {
    return pref[r+1] - pref[l];
}

ll left(int i, int c) {
    if (i-c+1 < 0) return 1e18;
    return 1ll*c*a[i] - sum(i-c+1, i);
}
ll right(int i, int c) {
    if (i+c-1 >= n) return 1e18;
    return sum(i, i+c-1) - 1ll*c*a[i];
}
ll costodd(int i, int c) {
    return left(i, c) + right(i, c);
}
ll costeven(int i, int c) {
    if (i == n-1) return 1e18;
    return left(i, c) + 1ll*c*(a[i+1]-a[i]) + right(i+1, c);
}

/*maximum x such that func(x) <= lim*/
int binsearch(function<ll(int)> func, int dl, int dr, ll lim) {
    int l = dl-1;
    int r = dr+1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (func(m) <= lim) l = m;
        else r = m;
    }
    return l;
}

int besthub(int R, int L, int X[], ll BVAL) {
    n = R;
    a = VI(n);
    B = BVAL;
    rep(i, n) a[i] = X[i];
    pref = VL(n+1);
    replr(i, 1, n) pref[i] = pref[i-1] + a[i-1];

    int ans = 0;
    rep(i, n) {
        /*cout << i << ": ";*/
        function<ll(int)> func1 = [&](int x){return costodd(i, x);};
        function<ll(int)> func2 = [&](int x){return costeven(i, x);};
        int oddans = binsearch(func1, 1, 2e5, B);
        int evenans = binsearch(func2, 1, 2e5, B);

        setmax(ans, oddans*2-1);
        setmax(ans, evenans*2);
        /*cout << oddans*2-1 << " " << evenans*2 << endl;*/
    }
    return ans;
}

Subtask #1
17.0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	0 ms	352 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	2 ms	348 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	2 ms	348 KB	Output is correct
24	Correct	2 ms	348 KB	Output is correct
25	Correct	2 ms	352 KB	Output is correct
26	Correct	2 ms	568 KB	Output is correct
27	Correct	2 ms	348 KB	Output is correct
28	Correct	2 ms	360 KB	Output is correct

Subtask #4
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	856 KB	Output is correct
2	Correct	5 ms	860 KB	Output is correct
3	Correct	39 ms	4728 KB	Output is correct
4	Correct	36 ms	4696 KB	Output is correct
5	Correct	19 ms	3612 KB	Output is correct
6	Correct	15 ms	3612 KB	Output is correct
7	Correct	34 ms	4444 KB	Output is correct
8	Correct	33 ms	4444 KB	Output is correct
9	Correct	16 ms	3380 KB	Output is correct
10	Correct	16 ms	3420 KB	Output is correct
11	Correct	38 ms	4896 KB	Output is correct
12	Correct	38 ms	4900 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	26 ms	4320 KB	Output is correct
16	Correct	28 ms	4188 KB	Output is correct
17	Correct	30 ms	4660 KB	Output is correct
18	Correct	32 ms	4444 KB	Output is correct
19	Correct	33 ms	4696 KB	Output is correct
20	Correct	36 ms	4700 KB	Output is correct

Submission #1007747

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 25.0 / 25.0

Subtask #3 26.0 / 26.0

Subtask #4 32.0 / 32.0

Subtask #1
17.0 / 17.0

Subtask #2
25.0 / 25.0

Subtask #3
26.0 / 26.0

Subtask #4
32.0 / 32.0