Submission #898763

#	Time	Username	Problem	Language	Result	Execution time	Memory
898763		Sir_Ahmed_Imran	Rice Hub (IOI11_ricehub)	C++17	100 / 100	14 ms	4564 KiB

ricehub

                              ///~~~LOTA~~~///
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 100000
ll a[MAXN];
ll b[MAXN];
bool check(ll n,ll l,ll r,vector<ll>& v,ll x){
    if(l==r) return 1;
    int mid=(l+r)/2;
    ll o=a[mid]+b[mid];
    o-=a[l]+(v[mid]-v[l])*l;
    o-=b[r-1]+(v[r-1]-v[mid])*(n-r);
    if(o>x) return 0;
    return 1;
}
int besthub(int N,int m,int X[],ll x){
    ll n=N;
    ll o,p,q;
    vector<ll> v;
    for(int i=0;i<n;i++)
        v.append(X[i]);
    a[0]=b[n-1]=o=p=q=0;
    for(ll i=1;i<n;i++)
        a[i]=a[i-1]+i*(v[i]-v[i-1]);
    for(ll i=n-2;i>=0;i--)
        b[i]=b[i+1]+(n-1-i)*(v[i+1]-v[i]);
    while(q<=n){
        if(check(n,p,q,v,x)){
            o=max(o,q-p);
            q++;
        }
        else p++;
    }
    return o;
}

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