Submission #516306

#	Time	Username	Problem	Language	Result	Execution time	Memory
516306		Jomnoi	Art Exhibition (JOI18_art)	C++17	100 / 100	233 ms	32684 KiB

art

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 5e5 + 10;
const long long INF = 1e18 + 7;

long long qs[N], dpl[N], dpr[N];

int main() {
    int n;
    cin >> n;

    vector <pair <long long, int>> vec;
    vec.emplace_back(0, 0);
    for(int i = 1; i <= n; i++) {
        long long a;
        int b;
        scanf(" %lld %d", &a, &b);
        vec.emplace_back(a, b);
    }
    sort(vec.begin(), vec.end());

    for(int i = 1; i <= n; i++) {
        qs[i] = qs[i - 1] + vec[i].second;
    }

    dpl[0] = dpr[n + 1] = -INF;
    for(int i = 1; i <= n; i++) {
        dpl[i] = max(dpl[i - 1], -qs[i - 1] + vec[i].first - vec[1].first);
    }
    for(int i = n; i >= 1; i--) {
        dpr[i] = max(dpr[i + 1], -qs[n] + qs[i] + vec[n].first - vec[i].first);
    }

    long long ans = -INF;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, qs[n] + dpl[i] + dpr[i] - vec[n].first + vec[1].first);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf(" %lld %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

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