Submission #1188674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188674		sonya	Happiness (Balkan15_HAPPINESS)	C++20	30 / 100	2096 ms	5704 KiB

happiness

#include "happiness.h"
#include <set>
#include <algorithm>

using namespace std;

multiset<long long> banknotes;
long long totalSum = 0;

bool is_happy_now() {
    if (banknotes.empty()) return true;
    if (*banknotes.begin() != 1) return false;

    long long reach = 0;
    for (long long value : banknotes) {
        if (value > reach + 1) return false;
        reach += value;
        // Early exit — няма нужда да проверяваме повече от totalSum
        if (reach >= totalSum) break;
    }

    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    banknotes.clear();
    totalSum = 0;

    for (int i = 0; i < coinsCount; ++i) {
        banknotes.insert(coins[i]);
        totalSum += coins[i];
    }

    return is_happy_now();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    if (event == -1) {  // Purchase — remove
        for (int i = 0; i < coinsCount; ++i) {
            auto it = banknotes.find(coins[i]);
            if (it != banknotes.end()) {
                banknotes.erase(it);
                totalSum -= coins[i];
            }
        }
    } else if (event == 1) {  // Wage — add
        for (int i = 0; i < coinsCount; ++i) {
            banknotes.insert(coins[i]);
            totalSum += coins[i];
        }
    }

    return is_happy_now();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40