Submission #414415

#	Time	Username	Problem	Language	Result	Execution time	Memory
414415		illyakr	Art Exhibition (JOI18_art)	C++14	100 / 100	910 ms	52172 KiB

art

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;
pair<int, int> a[501010];
multiset<pair<int, int> > now;
int ans = -8010101010101010101;
int32_t main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first >> a[i].second;
    sort(a + 1, a + 1 + n, [](pair<int, int> q, pair<int, int> w) {
         return q.first < w.first;
    });
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i].second;
        now.insert({-(sum - a[i].first), i});
    }
    int er = 0;
    for (int i = 1; i <= n; i++) {
        while (true) {
//            cout << now.size() << " " << i << " << " << endl;
            auto f = *now.begin();
            now.erase(now.begin());
//            cout << f.first << " " << f.second << "   " << i << "  !!!" << endl;
            if (f.second < i)continue;
            ans = max(ans, ((-f.first) - er) + a[i].first);
            now.insert(f);
            break;
        }
        er += a[i].second;
    }
    cout << ans;
}
/**
15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

6
4 1
1 5
10 3
9 1
4 2
5 3

3
2 3
11 2
4 5
*/

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50