oj.uz

Submission #856407

# Submission time Handle Problem Language Result Execution time Memory
856407 2023-10-03T12:01:21 Z overwatch9 Sails (IOI07_sails) C++17
30 / 100
 1000 ms 7024 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    priority_queue <pair <ll, int>> pq;
    vector <pair <int, int>> updates(n);
    int maxh = 0;
    for (int i = 0; i < n; i++) {
        cin >> updates[i].first >> updates[i].second;
        maxh = max(maxh, updates[i].first);
    }
    for (int i = 1; i <= maxh; i++)
        pq.push({0, i});
    sort(updates.begin(), updates.end());
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        priority_queue <pair <ll, int>> tp;
        int done = 0;
        while (done < updates[i].second) {
            pair <ll, int> x = pq.top();
            pq.pop();
            if (x.second <= updates[i].first) {
                ans += (-x.first);
                tp.push({x.first-1, x.second});
                done++;
            } else {
                tp.push(x);
            }
        }
        while (!tp.empty()) {
            pq.push(tp.top());
            tp.pop();
        }
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 28 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 608 KB Output is correct
2 Execution timed out 1037 ms 5512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 2092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 2140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1010 ms 3696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 6128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 7024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 6340 KB Time limit exceeded
2 Halted 0 ms 0 KB -