oj.uz

Submission #554922

# Submission time Handle Problem Language Result Execution time Memory
554922 2022-04-29T15:36:09 Z MohamedFaresNebili Sails (IOI07_sails) C++14
40 / 100
 1000 ms 4048 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        #define int ll

        const int oo = 1e9 + 7;

		int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            int N; cin >> N; vector<ii> arr(N);
            for(int l = 0; l < N; l++)
                cin >> arr[l].ff >> arr[l].ss;
            sort(arr.begin(), arr.end());
            int res = 0, curr = 0; priority_queue<int, vector<int>, greater<int>> pq;
            for(int l = 0; l < N; l++) {
                int H = arr[l].ff, K = arr[l].ss;
                for(int i = curr + 1; i <= H; i++)
                    pq.push(0);
                curr = max(curr, H); int calc = 0;
                vector<int> vec;
                while(calc < K) {
                    int v = pq.top(); pq.pop();
                    vec.pb({v + 1}); calc++;
                }
                for(auto u : vec) pq.push(u);
            }
            while(!pq.empty()) {
                int u = pq.top(); pq.pop();
                res += (u * (u - 1)) / 2;
            }
            cout << res << "\n";
		}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 416 KB Output is correct
2 Correct 168 ms 1416 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 1000 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 1097 ms 976 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 1079 ms 1508 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 1083 ms 4048 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 1086 ms 1892 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 1091 ms 2340 KB Time limit exceeded
2 Halted 0 ms 0 KB -