Submission #1214104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214104		yogesh_sane	Sails (IOI07_sails)	C++20	100 / 100	53 ms	4424 KiB

sails

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<pair<int, int>>masts(n);
    multiset<int> ms;
    for(int i=0; i<n; i++)
        cin>>masts[i].first>>masts[i].second;
    sort(masts.begin(),masts.end());
    ms.insert(0);
    for(int i=0; i < n; i++){
        int h = masts[i].first;
        int k = masts[i].second;
        ms.insert(h);
        auto p = ms.upper_bound(h-k);
        auto q = prev(p);
        int aux = k + *p + *q - h;
        if(q!= ms.begin()) 
            ms.erase(q);
        ms.erase(p);
        ms.insert(aux);
    }
    long long ans=0, cnt=0;
    for(auto it = --ms.end(); it != ms.begin(); it--, cnt++)
        ans += cnt*(*it);
    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