Submission #1272485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272485		witek_cpp	Let's Win the Election (JOI22_ho_t3)	C++20	5 / 100	4 ms	352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<pair<int,int>> states(N);
    for (int i=0;i<N;i++) cin >> states[i].first >> states[i].second; // Ai, Bi

    const ll INF = 4e18;
    ll ans = INF;

    // posortowane po Ai i Bi
    vector<int> orderA(N), orderB;
    iota(orderA.begin(), orderA.end(), 0);
    sort(orderA.begin(), orderA.end(), [&](int i,int j){ return states[i].first < states[j].first; });

    for (int i=0;i<N;i++) if (states[i].second != -1) orderB.push_back(i);
    sort(orderB.begin(), orderB.end(), [&](int i,int j){ return states[i].second < states[j].second; });

    // prefix sums dla Ai
    vector<ll> prefA(N+1,0);
    for (int i=0;i<N;i++) prefA[i+1] = prefA[i] + states[orderA[i]].first;

    // prefix sums dla Bi
    vector<ll> prefB(orderB.size()+1,0);
    for (int i=0;i<(int)orderB.size();i++) prefB[i+1] = prefB[i] + states[orderB[i]].second;

    for (int m=0;m<=orderB.size();m++) { // ilu pomagierów kupimy
        if (m > orderB.size()) break;
        if (m > 0 && prefB[m] >= INF) continue;

        // wybieramy K głosów (uwzględniając, że stany pomagierów mogą też być głosem)
        // żeby to obsłużyć łatwo: weźmy listę wszystkich Ai, ale dla stanów z kupionym pomagierem weźmy min(Ai,0) w praktyce -> Ai
        // implementacja: po prostu wybieramy minK spośród wszystkich stanów
        vector<int> used(orderB.begin(), orderB.begin()+m);
        vector<bool> mark(N,false);
        for (int id: used) mark[id]=true;

        // zbieramy wszystkie Ai, a stany z pomagierami są już zaznaczone
        vector<int> candidates;
        for (int i=0;i<N;i++) candidates.push_back(states[i].first);
        sort(candidates.begin(), candidates.end());

        if (K > N) continue;
        ll sumA = 0;
        for (int i=0;i<K;i++) sumA += candidates[i];

        ll total = prefB[m] + sumA;
        ll time = (total + m) / (m+1); // ceil dzielenia
        ans = min(ans, time);
    }

    cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23