백준 2109번 순회강연 C++

https://www.acmicpc.net/problem/2109

2109번: 순회강연

 

n번째 날 가능한 강연 중 가장 돈을 많이 받는 강연 : n ~ 마지막 날 중 가장 돈을 많이 받는 강연

제일 뒤에 날부터 검사

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<multiset<int>> v(10001, multiset<int>());

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int p, d;
        cin >> p >> d;
        v[d].insert(p);
    }
    int money = 0;
    for (int now = 10000; now >= 1; now--) {
        int maxMoney = 0;
        int maxIdx = -1;
        for (int j = now; j <= 10000; j++) {
            if (v[j].empty()) continue;
            auto it = v[j].end();
            --it;
            int currMoney = *it;
            if (currMoney > maxMoney) {
                maxMoney = currMoney;
                maxIdx = j;
            }
        }
        if (maxMoney == 0) continue;
        money += maxMoney;
        auto it = v[maxIdx].end();
        --it;
        v[maxIdx].erase(it);
    }
    cout << money;
}