Submission #964009

#	Time	Username	Problem	Language	Result	Execution time	Memory
964009		Hugo1729	Rice Hub (IOI11_ricehub)	C++11	42 / 100	186 ms	262144 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
typedef long long ll;

ll a[5000*2][5001*2], b[5000*2][5001*2];

int besthub(int R, int L, int X[], long long B){

    for(int i=0;i<R;i++){
        for(int j=0;j<=R;j++){
            if(j==0){
                a[i][j]=0;
            }
            else if(j-1<=i){
                a[i][j]=a[i-1][j-1]+(X[i]-X[i-1])*(j-1);
            }else{
                a[i][j]=LLONG_MAX/3;
            }
        }
    }

    for(int i=R-1;i>=0;i--){
        for(int j=0;j<=R;j++){
            if(j==0){
                b[i][j]=0;
            }
            else if(j<=R-i-1){
                b[i][j]=b[i+1][j-1]+(X[i+1]-X[i])*j;
            }else{
                b[i][j]=LLONG_MAX/3;
            }
        }
    }

    ll ans=0;

    // for(int i=0;i<R;i++){
    //     for(int j=0;j<=R;j++){
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    // for(int i=0;i<R;i++){
    //     for(int j=0;j<=R;j++){
    //         cout << b[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    for(int i=0;i<R;i++){
        ll ptr=R;
        for(int j=0;j<=R;j++){
            if(a[i][j]>B||ptr<0)break;
            while(a[i][j]+b[i][ptr]>B){
                ptr--;
                if(ptr<0)break;
            }
            if(ptr<0)break;

            // cout << i << ' ' << j << ' ' << ptr << '\n';

            ans=max(ans,j+ptr);
        }
    }



    return ans;
}

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