Submission #867471

#	Time	Username	Problem	Language	Result	Execution time	Memory
867471		HuyQuang_re_Zero	Rice Hub (IOI11_ricehub)	C++14	100 / 100	14 ms	3680 KiB

ricehub

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define maxn 200005
#include "ricehub.h"
using namespace std;
struct International_Olympiad_in_Informatics
{
    ll i,f[maxn];
    ll SUM(int l,int r) { return f[r]-f[l-1]; }
    int Work(int n,int X,int x[],ll m)
    {
        int res=0;
        for(i=1;i<=n;i++) f[i]=f[i-1]+x[i];
        for(i=1;i<=n;i++)
        {
            int l=1,r=min(i,n-i+1);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(SUM(i,i+mid-1)-SUM(i-mid+1,i)<=m)
                    l=mid;
                else r=mid-1;
            }
            ll k=SUM(i,i+l-1)-SUM(i-l+1,i);
            int val=2*l-1+((i>l && k+x[i]-x[i-l]<=m) || (i+l<=n && k+x[i+l]-x[i]<=m));
            res=max(res,val);
        }
        return res;
    }
} IOI;
int besthub(int r,int l,int x[],ll b)
{
    for(int i=r;i>=1;i--) x[i]=x[i-1];
    return IOI.Work(r,l,x,b);
}
/*
int main()
{
    freopen("ricehub.inp","r",stdin);
    freopen("ricehub.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int r,l,b;
    cin>>r>>l;
    int x[r+1];
    for(int i=0;i<r;i++) cin>>x[i];
    cin>>b;
    cout<<besthub(r,l,x,b);
}*/

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