제출 #1341311

#제출 시각아이디문제언어결과실행 시간메모리
1341311kantaponzArt Exhibition (JOI18_art)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 5e5 + 5;

int n;
ll a[nx], qs[nx];
ll dp[nx];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    vector<pair<int,int>> v;
    for (int i = 1; i <= n; i++) cin >> a[i] >> qs[i], v.emplace_back(a[i], qs[i]);
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; i++) {
        a[i] = v[i - 1].first;
        qs[i] = v[i - 1].second;
        qs[i] += qs[i - 1];
    }
    ll ans = -1e18;
    fill(dp, dp + n + 1, -1e18);
    for (int i = 1; i <= n; i++) {
        dp[i] = max(dp[i - 1], a[i] - qs[i - 1]);
        ans = max(ans, -a[i] + qs[i] + dp[i]);
        //cout << -a[i] + qs[i] + dp[i] << " " << a[i] - qs[i - 1] << endl;
    }
    cout << ans;
}

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

7

3
2 3
11 2
4 5

6
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...