oj.uz

Submission #950515

# Submission time Handle Problem Language Result Execution time Memory
950515 2024-03-20T11:35:55 Z irmuun Rice Hub (IOI11_ricehub) C++17
0 / 100
 3 ms 604 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int besthub(int R,int L,int X[],ll B){
    ll sum[R+1];
    sum[0]=0;
    for(int i=0;i<R;i++){
        sum[i+1]=sum[i]+X[i];
    }
    int ans=0;
    for(int i=1;i<=R;i++){
        int l=0,r=R;
        while(l<r){
            int mid=(l+r+1)/2;
            if(i-mid<0||i+mid>R){
                r=mid-1;
                continue;
            }
            ll cost=1ll*X[i-1]*mid-(sum[i-1]-(i-mid>0?sum[i-mid-1]:0))+(sum[i+mid]-sum[i])-1ll*X[i-1]*mid;
            if(cost<=B){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        ans=max(ans,l*2+1);
    }
    for(int i=1;i<R;i++){
        if((ll)X[i]-(ll)X[i-1]>B) continue;
        int l=0,r=R;
        while(l<r){
            int mid=(l+r+1)/2;
            if(i-mid<0||i+mid+1>R){
                r=mid-1;
                continue;
            }
            ll cost=1ll*X[i-1]*mid-(sum[i-1]-(i-mid>0?sum[i-mid-1]:0))+(sum[i+mid+1]-sum[i+1])-1ll*X[i]*mid;
            cost+=X[i]-X[i-1];
            if(cost<=B){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        ans=max(ans,l*2+2);
    }
    return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Incorrect 3 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -