Submission #670406

#	Time	Username	Problem	Language	Result	Execution time	Memory
670406		illyakr	Art Exhibition (JOI18_art)	C++14	100 / 100	483 ms	20956 KiB

art

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

using namespace std;

int n;
pair<int, int> t[501010];

int my() {
    sort(t + 1, t + 1 + n, [](pair<int, int> q, pair<int, int> w) {
         return q.first < w.first;
    });
//    cout << endl;
//    for (int i = 1; i <= n; i++)
//        cout << t[i].first << " " << t[i].second << endl;
//        cout << endl;

    int sum = 0;
    int MX = 0;

    int ans = -1010101010101010101;
    for (int i = 1; i <= n; i++) {
        sum += t[i].second;
        ans = max(ans, sum - t[i].first + MX);
        ans = max(ans, t[i].second);
        MX = max(MX, -(sum - t[i].second) + t[i].first);
//        cout << i << " <<< " << -(sum-t[i].second) + t[i].first << endl;
    }
    return ans;
}
int brute() {
    int ans = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        int cur = 0;
        int MX = 0, MN = 1010101010101010101;
        for (int i = 0; i < n; i++) {
            if (1 & (mask >> i)) {
                cur += t[i + 1].second;
                MX = max(MX, t[i + 1].first);
                MN = min(MN, t[i + 1].first);
            }
        }
        ans = max(ans, cur - MX + MN);
    }
    return ans;
}

int32_t main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> t[i].first >> t[i].second;
    cout << my();
//    srand(time(0));
//    for (int id = 1; id <= 10000; id++) {
//        n = rand() % 10 + 1;
//        for (int i = 1; i <= n; i++) {
//            t[i].first = rand() % 10 + 1;
//            t[i].second = rand() % 10 + 1;
//        }
//        int f = my();
//        int s = brute();
//        if (f != s) {
//            cout << n << endl;
//            for (int i = 1; i <= n; i++) {
//                cout << t[i].first << " " << t[i].second << endl;
//            }
//            cout << endl;
//            cout << f << " " << s << endl;
//            exit(1);
//        }
//    }
}

/**
2
7 1
7 2

4 3



5
8 1
7 7
6 5
6 5
1 1

12 16
*/

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