제출 #816622

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

ricehub

/**
 * Quite trivial?
 * 
 * Time Complexity: O(R)            (two-pointer, binary search)
 * Implementation 1                 (Full solution)
*/

#include <bits/stdc++.h>
#include "ricehub.h"

typedef long long   ll;


// Calculate the cost of grabbing all rice hubs between a and b, inclusive.
inline ll calc_cost(const std::vector<ll>& prefix_sum, int a, int b) {
    int mid = (a + b) / 2, mid_val = prefix_sum[mid + 1] - prefix_sum[mid];
    ll c1 = (mid - a + 1) * mid_val - (prefix_sum[mid + 1] - prefix_sum[a]);
    ll c2 = (prefix_sum[b + 1] - prefix_sum[mid + 1]) - (b - mid) * mid_val;
    return c1 + c2;
}

int besthub(int R, int L, int X[], ll B) {
    std::vector<ll> prefix_sum(R + 1);
    prefix_sum[0] = 0;
    for (int k = 0; k < R; k++)
        prefix_sum[k + 1] = prefix_sum[k] + X[k];
    int max_rice = 0;
    for (int a = 0, b = 0; b < R; a++) {
        while (b < R && calc_cost(prefix_sum, a, b) <= B)
            b++;
        max_rice = std::max(max_rice, b - a);
    }
    return max_rice;
}

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