Submission #1249198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249198		1ncogn1to	Sails (IOI07_sails)	C++20	0 / 100	1095 ms	4032 KiB

sails

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

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

    int N;
    cin >> N;
    vector<pair<int,int>> mast(N);
    int maxH = 0;
    for(int i = 0; i < N; i++){
        cin >> mast[i].first >> mast[i].second;
        maxH = max(maxH, mast[i].first);
    }
    // sortujemy maszty rosnąco po wysokości H
    sort(mast.begin(), mast.end());

    // S[L] = aktualna liczba żagli na poziomie L
    vector<ll> S(maxH+1, 0);

    // min‑heap par (S[L], L)
    // używamy greater<>, bo chcemy najmniejsze S[L] na szczycie
    priority_queue<
        pair<ll,int>,
        vector<pair<ll,int>>,
        greater<pair<ll,int>>
    > pq;

    // inicjalizujemy kolejkę poziomami 1..maxH ze stanem 0
    for(int L = 1; L <= maxH; L++){
        pq.emplace(0LL, L);
    }

    // przetwarzamy każdy maszt
    for(auto &p : mast){
        int H = p.first;
        int K = p.second;

        vector<int> chosen;
        chosen.reserve(K);

        // wybieramy K razy poziom o najmniejszym obciążeniu
        while((int)chosen.size() < K){
            auto [s, L] = pq.top();
            pq.pop();
            // pomijamy nieaktualne wpisy:
            // 1) poziom wykracza poza zasięg H
            // 2) zapisane s != S[L]
            if(L > H || s != S[L]) continue;

            // akceptujemy poziom L
            chosen.push_back(L);
            // zwiększamy obciążenie w tablicy
            S[L]++;
        }

        // wstawiamy zaktualizowane stany z powrotem do kolejki
        for(int L : chosen){
            pq.emplace(S[L], L);
        }
    }

    // po wszystkim liczymy total inefficiency = Σ S[L]*(S[L]-1)/2
    ll result = 0;
    for(int L = 1; L <= maxH; L++){
        result += S[L] * (S[L] - 1) / 2;
    }

    cout << result << "\n";
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10