제출 #54861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54861		FLDutchman	쌀 창고 (IOI11_ricehub)	C++14	68 / 100	34 ms	3324 KiB

ricehub

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

typedef long long ll;
typedef vector<ll> vi;

vi prefix, suffix;
vi rice;

ll MAX;

int cost(int l, int r){
    int m = (l+r)/2;
    ll c = prefix[r] - prefix[m] - rice[m] * (r-m);
    c += suffix[l] - suffix[m] - (MAX - rice[m]) * (m-l);
    return c;
}

bool possible(int l, int r, ll B){
    //cout <<l << " " << r << " " << cost(l,r) << endl;
    return cost(l, r) <= B;
}

int besthub(int R, int L, int X[], ll B)
{
    MAX = L;
    rice.resize(R);
    for(int i = 0; i < R; i++) rice[i] = X[i];
    prefix.assign(R+1, 0); suffix.assign(R+1, 0);
    for(int i = 1; i <= R; i++) prefix[i] = prefix[i-1] + rice[i-1];
    for(int i = R-1; i >= 0; i--) suffix[i] = suffix[i+1] + L - rice[i];
    ll l = 0, r = 0;
    ll best = -1;
    while(!(l == R and r == R)){
        while(possible(l, r, B)){
            best = max(best, r-l);
            if(r < R) r++;
            else break;
        }
        l++;
    }

    return best;
}
/*
int test[] = {1, 2, 10, 12, 14};
int main(){
    
    cout << besthub(5, 20, test, 6)<<endl;
}
*/

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