Submission #62163

#	Time	Username	Problem	Language	Result	Execution time	Memory
62163		reality	Rice Hub (IOI11_ricehub)	C++17	100 / 100	54 ms	16508 KiB

ricehub

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "ricehub.h"


const int N = (int)(1e6) + 5;

ll s[N];

ll ss[N];

ll get(int l,int m,int r)
{
    return (ss[r] - ss[m]) - (r - m) * s[m] + (m - l) * s[m] - (ss[m - 1] - ss[l - 1]);
}

int besthub(int N, int L, int X[], ll B)
{
    int n = N;
    int m = L;
    ll k = B;
    int ans = 0;
    for (int i = 0;i < n;++i)
        s[i + 1] = X[i],ss[i + 1] = ss[i] + s[i + 1];
    for (int i = 1;i <= n;++i)
    {
        int len = 0;
        for (int t = 1 << 17;t;t /= 2)
            if (get(max(1,i - len - t),i,min(n,i + len + t)) <= k)
                len += t;
        int L = max(1,i - len);
        int R = min(n,i + len);
        if (get(L,i,R) <= k)
            ans = max(ans,R - L + 1);
        if (L > 1 && get(L - 1,i,R) <= k)
            ans = max(ans,R - L + 2);
        if (R < n && get(L,i,R + 1) <= k)
            ans = max(ans,R - L + 2);
    }
    return ans;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:32:9: warning: unused variable 'm' [-Wunused-variable]
     int m = L;
         ^

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