제출 #1324044

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

ricehub

#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

/**
 * besthub funksiyasi maksimal guruch miqdorini qaytaradi.
 * R - maydonlar soni, L - maksimal koordinata, X - koordinatalar, B - budjet.
 */
int besthub(int R, int L, int X[], ll B) {
    // Xarajatni O(1) da hisoblash uchun prefiks yig'indilari massivi
    vector<ll> prefix_sum(R + 1, 0);
    for (int i = 0; i < R; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + X[i];
    }

    int max_fields = 0;
    int left = 0;

    // Suriluvchi oyna (Sliding Window)
    for (int right = 0; right < R; right++) {
        // Markazni medianada (o'rtadagi maydonda) joylashtiramiz
        int median_idx = (left + right) / 2;
        ll median_val = X[median_idx];

        // Markazdan chapdagi maydonlar xarajati
        ll left_size = median_idx - left;
        ll cost_left = median_val * left_size - (prefix_sum[median_idx] - prefix_sum[left]);

        // Markazdan o'ngdagi maydonlar xarajati
        ll right_size = right - median_idx;
        ll cost_right = (prefix_sum[right + 1] - prefix_sum[median_idx + 1]) - median_val * right_size;

        // Agar umumiy xarajat budjetdan oshsa, chap tomondan oynani qisqartiramiz
        while (cost_left + cost_right > B && left < right) {
            left++;
            median_idx = (left + right) / 2;
            median_val = X[median_idx];
            
            left_size = median_idx - left;
            cost_left = median_val * left_size - (prefix_sum[median_idx] - prefix_sum[left]);
            
            right_size = right - median_idx;
            cost_right = (prefix_sum[right + 1] - prefix_sum[median_idx + 1]) - median_val * right_size;
        }

        // Maksimal qamrovni yangilaymiz
        max_fields = max(max_fields, right - left + 1);
    }

    return max_fields;
}

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