제출 #1324247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324247		sh_qaxxorov_571	Sure Bet (CEOI17_sure)	C++20	100 / 100	45 ms	1996 KiB

sure

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

/**
 * CEOI 2017 - Sure Bet
 * Vaqt murakkabligi: O(N log N) - saralash tufayli 
 * Xotira murakkabligi: O(N) [cite: 4]
 */

int main() {
    // Kirish va chiqishni tezlashtirish
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0; // Bukmekerlar sonini o'qish [cite: 19, 43]

    vector<double> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i]; // a_i va b_i koeffitsientlarini o'qish [cite: 19, 45, 46, 47, 48]
    }

    // Eng katta koeffitsientlarni olish uchun har bir natijani alohida saralaymiz 
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    double max_profit = 0.0;
    double sum_a = 0.0;
    double sum_b = 0.0;
    int ptr_b = 0;

    // 1-natija uchun tikilgan tikishlar sonini (i) oshirib boramiz [cite: 14]
    for (int i = 0; i <= n; i++) {
        if (i > 0) sum_a += a[i - 1];

        // 2-natija uchun summani (sum_b) muvozanatlashtirish uchun ptr_b ni suramiz [cite: 15, 51]
        while (ptr_b < n) {
            double current_profit = min(sum_a, sum_b + b[ptr_b]) - (i + ptr_b + 1);
            
            // Agar yangi tikish qo'shish foydani oshirsa yoki muvozanatni yaxshilasa
            if (sum_b + b[ptr_b] < sum_a) {
                sum_b += b[ptr_b];
                ptr_b++;
                max_profit = max(max_profit, min(sum_a, sum_b) - (i + ptr_b));
            } else {
                // Agar sum_b sum_a dan o'tib ketsa, bu nuqtada ham foydani tekshirib to'xtaymiz
                max_profit = max(max_profit, min(sum_a, sum_b + b[ptr_b]) - (i + ptr_b + 1));
                break;
            }
        }
        
        // Har bir qadamda kafolatlangan foydani yangilab boramiz 
        max_profit = max(max_profit, min(sum_a, sum_b) - (i + ptr_b));
    }

    // Natijani verguldan keyin 4 ta raqam bilan chiqarish [cite: 34, 36]
    cout << fixed << setprecision(4) << max_profit << endl;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40