Submission #1049376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049376		AndreasK	Rice Hub (IOI11_ricehub)	C++14	100 / 100	13 ms	4528 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
 
#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define ii pair <int,int>
#define vi vector <int>
#define iii pair <int,ii>
#define vii vector <ii>
#define vc vector <char>
#define vb vector <bool>
 
int besthub(int R, int L, int X[], long long B)
{
    #define int long long
    int pre[R];
    int ttl=0;
    for (int c=0;c<R;c++){
        ttl+=X[c];
        pre[c]=ttl;
    }
    int mx=0;
    for (int r=0;r<R;r++){
        int ll=r,rr=(R-1+r)/2,mid;
        while (ll<=rr){
            mid=(ll+rr)/2;
            int f=0;
            if (r==0){
                f+=(mid-r+1)*X[mid]-pre[mid];
            }
            else{
                f+=(mid-r+1)*X[mid]-pre[mid]+pre[r-1];
            }
            int f1;
            if (mid!=0){
                f1=f+pre[mid+(mid-r)]-pre[mid-1]-(mid-r+1)*X[mid];
            }
            else{
                f1=f+pre[mid+(mid-r)]-(mid-r+1)*X[mid];
            }
            int f2=LLONG_MAX;
            if (mid+mid-r+1<R){
                if (mid!=0){
                    f2=f+pre[mid+(mid-r+1)]-pre[mid-1]-(mid-r+2)*X[mid];
                }
                else{
                    f2=f+pre[mid+(mid-r+1)]-(mid-r+2)*X[mid];
                }
            }
            if (f1<=B){
                mx=max(mx,2*(mid-r)+1);
            }
            if (f2<=B){
                mx=max(mx,2*(mid-r)+2);
            }
            if (f1<=B){
                ll=mid+1;
            }
            else
                rr=mid-1;
        }
    }
    return mx;
}
 
/*int32_t main(){
    designed by AndreasK
    int R,L,B;
    cin>>R>>L>>B;
    int X[R];
    for (auto &c:X)
        cin>>c;
    cout<<besthub(R,L,X,B);
return 0;}*/

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