Submission #1133468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133468		lopkus	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	2376 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18+10;
const int maxn=1e5+10;
ll v[maxn], sp[maxn], n;
bool check(int x, ll lim){
    ll tirar=n-x;
    ll cost=inf;
    for(ll i=0;i<=tirar;i++){
        // vou checar se os i primeiros caras n existem e os x-i ultimos caras n existem tbm
        // o "1" vai ser o 1+i, e o "n", sera o n-(x-i);
        // portanto a mediana será: piso(((1+i)+(n-(x-i))+1)/2)
        ll opt=((x+1)/2)+i;
        ll at=v[opt]*(opt-i)-(sp[opt]-sp[i])+(sp[n-(tirar-i)]-sp[opt])-v[opt]*(n-(tirar-i)-opt);
        // o custo eh |v[opt]-v[j]|, sendo 1+i<=j<=(n-(x-i))
        // temos q se j<=opt => |v[opt]-v[j]|=v[opt]-v[j] (ou seja: qtd*v[opt]-soma de todos menores)
        // e caso contrário (j>opt)=>|v[opt]-v[j]|=v[j]-v[opt] (ou seja: soma dos maiores-qtd*v[opt])
        cost=min(cost,at);
    }
    return cost<=lim;
}
int besthub(int R, int L, int X[], ll B)
{
    n=R;
    for(int i=1;i<=n;i++) v[i]=X[i-1];
    for(int i=1;i<=n;i++) sp[i]=sp[i-1]+v[i];
    int l=1, r=n;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid,B)) l=mid;
        else r=mid-1;
    }
    return l;
}

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