Submission #348756

#	Time	Username	Problem	Language	Result	Execution time	Memory
348756		apostoldaniel854	Sails (IOI07_sails)	C++14	100 / 100	94 ms	7016 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10