oj.uz

Submission #348756

# Submission time Handle Problem Language Result Execution time Memory
348756 2021-01-15T16:14:27 Z apostoldaniel854 Sails (IOI07_sails) C++14
100 / 100
 94 ms 7016 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"


struct Mast {
    int height;
    int cnt;
    bool operator < (const Mast &other) const {
        return height < other.height;
    }
};

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    vector <Mast> masts;
    for (int i = 1; i <= n; i++) {
        int height, cnt;
        cin >> height >> cnt;
        masts.pb ({height, cnt});
    }
    sort (masts.begin (), masts.end ());
    multiset <int> diff;
    for (int i = 1; i <= n; i++)
        diff.insert (0);
    for (Mast mast : masts) {
        int height = mast.height;
        int cnt = mast.cnt;
        auto it = diff.lower_bound (height - cnt + 1);
        auto prv = prev (it);
        if (it != diff.end ()) {
            cnt -= height - *it;
            diff.erase (it);
            diff.insert (height);
        }
        int value = *prv;
        diff.erase (prv);
        diff.insert (value + cnt);
    }
    int prv = 0;
    ll ans = 0;
    ll cnt = n;
    for (int d : diff) {
        ans += (d - prv) * cnt * (cnt - 1) / 2;
        cnt--;
        prv = d;
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 748 KB Output is correct
2 Correct 20 ms 2288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2288 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3632 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5352 KB Output is correct
2 Correct 57 ms 5352 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 6376 KB Output is correct
2 Correct 65 ms 5992 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7016 KB Output is correct
2 Correct 79 ms 6860 KB Output is correct