Submission #344295

#	Time	Username	Problem	Language	Result	Execution time	Memory
344295		NicolaAbusaad2014	Rice Hub (IOI11_ricehub)	C++14	100 / 100	38 ms	4192 KiB

ricehub

/**
 * Prof.Nicola
**/
#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T1,class T2> pair<T1,T2> mp(T1&x,T2&z){return make_pair(x,z);}
vector<long long>v,pre;
long long cost,n;
long long calc(long long l,long long r)
{
    long long mid=(l+r)/2;
    long long ret=(pre[r+1]-pre[mid+1])-((r-mid)*v[mid])+(((mid-l)*v[mid])-(pre[mid]-pre[l]));
    return ret;
}
long long right(long l,long r)
{
    if(l==r){
        return l;
    }
    long long z=r-l,x=l;
    while(z&(z-1)){
        z=z&(z-1);
    }
    while(z){
        if(x+z<=r&&calc(l,x+z)<=cost){
            x+=z;
        }
        z/=2;
    }
    return x;
}
int besthub(int R, int L, int X[], long long B)
{
    cost=B;
    n=R;
    pre.push_back(0);
    for(long i=0;i<n;i++){
        v.push_back(X[i]);
    }
    for(long i=0;i<n;i++){
        pre.push_back(pre[i]+X[i]);
    }
    int ans=1;
    for(long i=0;i<n;i++){
        ans=max(ans,(int)(right(i,n-1)-i+1));
    }
    return ans;
}

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