Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- #include <vector>
- #include <algorithm>
- #include <queue>
- int main()
- {
- int n, m;
- cin >> n >> m;
- vector<pair<int, int>> v;
- for (int i = 0; i < m; i++)
- {
- int s, l;
- cin >> s >> l;
- v.push_back(pair<int, int>(s, l));
- }
- sort(v.begin(), v.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
- if (p1.first == p2.first)
- return p1.second > p2.second;
- return p1.first < p2.first;
- });
- priority_queue<int, vector<int>, std::greater<int>> studios;
- for (int i = 1; i <= n; i++)
- studios.push(i);
- priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, std::greater<pair<pair<int, int>, int>>> pq;
- for (int i = 0; i < m; i++)
- {
- int currArr = v[i].first;
- while (!pq.empty() && pq.top().first.first <= currArr)
- {
- auto p = pq.top();
- studios.push(p.second);
- pq.pop();
- }
- if (studios.empty() && !pq.empty())
- {
- auto curr = pq.top();
- pq.pop();
- pq.push({ {curr.first.first + v[i].second, curr.first.second}, curr.first.first });
- }
- else {
- pq.push({ {v[i].second + v[i].first, studios.top()}, v[i].first });
- studios.pop();
- }
- }
- pair<pair<int, int>, int> p;
- while (!pq.empty())
- {
- p = pq.top();
- pq.pop();
- }
- cout << p.first.first << " " << p.first.second;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement