Submission #1024096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024096		idas	Rice Hub (IOI11_ricehub)	C++11	100 / 100	10 ms	4624 KiB

ricehub

#include "ricehub.h"

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)

typedef long long ll;

const int N=1e5+10;
ll p[N], s[N];

ll l_cost(int l, int r, int max_len, int x[])
{
    ll ret=p[r+1]-p[l];
    ret-=1LL*(r-l+1)*(max_len-x[r]);
    return ret;
}

ll r_cost(int l, int r, int max_len, int x[])
{
    ll ret=s[l]-s[r+1];
    ret-=1LL*(r-l+1)*x[l];
    return ret;
}

bool can(int val, int r, int l, int x[], long long b)
{
    FOR(i, 0, r)
    {
        if(i+val-1>=r) break;
        int lb=i, rb=i+val-1, med=(lb+rb)/2;
        ll cost=l_cost(lb, med, l, x)+r_cost(med, rb, l, x);
        if(cost<=b) return true;
    }
    return false;
}

int besthub(int r, int l, int x[], long long b)
{
    FOR(i, 1, r+1)
    {
        p[i]=p[i-1];
        p[i]+=l-x[i-1];
    }

    for(int i=r-1; i>=0; i--){
        s[i]=s[i+1];
        s[i]+=x[i];
    }

    int lft=0, rgt=r;
    while(lft<rgt){
        int m=(lft+rgt+1)/2;
        if(can(m, r, l, x, b)) lft=m;
        else rgt=m-1;
    }

    return lft;
}

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