제출 #1169949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169949		mnbvcxz123	학교 설립 (IZhO13_school)	C++20	100 / 100	69 ms	9668 KiB

school

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct City {
    int A, B;
    int d; // A - B
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, S;
    cin >> N >> M >> S;
    vector<City> cities(N);
    for (int i = 0; i < N; i++){
        cin >> cities[i].A >> cities[i].B;
        cities[i].d = cities[i].A - cities[i].B;
    }
    
    // Sort cities descending by (A - B)
    sort(cities.begin(), cities.end(), [](const City &c1, const City &c2){
        return c1.d > c2.d;
    });
    
    // Handle cases where one type of school is 0.
    if(M == 0 && S > 0){
        // Choose S cities maximizing B.
        priority_queue<int, vector<int>, greater<int>> minHeap;
        ll sum = 0;
        for (int i = 0; i < N; i++){
            minHeap.push(cities[i].B);
            sum += cities[i].B;
            if(minHeap.size() > (size_t)S){
                sum -= minHeap.top();
                minHeap.pop();
            }
        }
        cout << sum << "\n";
        return 0;
    }
    if(S == 0 && M > 0){
        // Choose M cities maximizing A.
        priority_queue<int, vector<int>, greater<int>> minHeap;
        ll sum = 0;
        for (int i = 0; i < N; i++){
            minHeap.push(cities[i].A);
            sum += cities[i].A;
            if(minHeap.size() > (size_t)M){
                sum -= minHeap.top();
                minHeap.pop();
            }
        }
        cout << sum << "\n";
        return 0;
    }
    if(M == 0 && S == 0){
        cout << 0 << "\n";
        return 0;
    }
    
    // Compute prefix best sums for selecting exactly M cities (for music) 
    // from indices [0...i] (using the A values).
    vector<ll> pref(N, -1);
    priority_queue<int, vector<int>, greater<int>> heapA;
    ll sumA = 0;
    for (int i = 0; i < N; i++){
        heapA.push(cities[i].A);
        sumA += cities[i].A;
        if(heapA.size() > (size_t)M){
            sumA -= heapA.top();
            heapA.pop();
        }
        if(heapA.size() == (size_t)M){
            pref[i] = sumA;
        }
    }
    
    // Compute suffix best sums for selecting exactly S cities (for sports)
    // from indices [i...N-1] (using the B values).
    vector<ll> suf(N+1, -1);
    priority_queue<int, vector<int>, greater<int>> heapB;
    ll sumB = 0;
    for (int i = N-1; i >= 0; i--){
        heapB.push(cities[i].B);
        sumB += cities[i].B;
        if(heapB.size() > (size_t)S){
            sumB -= heapB.top();
            heapB.pop();
        }
        if(heapB.size() == (size_t)S){
            suf[i] = sumB;
        }
    }
    
    // Try every valid "cut". For a cut index i (0-indexed), we assume that:
    // - From cities[0...i] we can pick M cities for music (pref[i] is defined if i >= M-1),
    // - From cities[i+1...N-1] we can pick S cities for sports (suf[i+1] is defined if i <= N-S-1).
    // We then take the maximum of pref[i] + suf[i+1].
    ll ans = 0;
    for (int i = M - 1; i <= N - S - 1; i++){
        if(pref[i] < 0 || suf[i+1] < 0) continue;
        ans = max(ans, pref[i] + suf[i+1]);
    }
    
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100