제출 #1251171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251171		lambd47	쌀 창고 (IOI11_ricehub)	C++20	100 / 100	10 ms	720 KiB

ricehub

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

#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()


int besthub(int n, int troll, int vec[], long long B){

    int l,r;
    int med;
    ll val;
    auto ini=[&](int x)->void{
        l=0;
        r=x-1;
        med=vec[(l+r)/2];
        val=0;
        L(i,l,r)val+=abs(med-vec[i]);
    };
    auto upd=[&]()->void{
        val-=abs(vec[l]-med);
        l++;
        r++;
        int nmed=vec[(l+r)/2];
        val+=(nmed-med)*((l+r)/2-l);
        val-=(nmed-med)*(r-(l+r)/2);
        val+=abs(vec[r]-nmed);
        med=nmed;
    };
    auto testa=[&](int m)->bool{
        ini(m);
        ll resp=val;
        while(r!=n-1){
            upd();
            resp=min(resp,val);
        }
        return resp<=B;
    };
    int lo=1, hi=n;

    int resp=1;
    while(lo<=hi){
        int m=(lo+hi)/2;
        if(testa(m)){
            lo=m+1;
            resp=m;
        }
        else hi=m-1;
    }
    return resp;



}

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