제출 #1323216

#제출 시각아이디문제언어결과실행 시간메모리
1323216b_esma101811Art Exhibition (JOI18_art)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 2e5 + 10, MOD = 1e9 + 7;
int dp[MAX], dp2[MAX];
void solve() {
    vector<pair<int, int>> vt;
    map<int, int> mp;
    int n;
    cin >> n;
    int a[n + 1];
    int b[n + 1];
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        vt.push_back({a[i], b[i]});
    }
    sort(vt.begin(), vt.end());
    int pref[n + 1];
    pref[0] = 0;
    for(int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + vt[i].second;
        mp[vt[i].first] = i;
    }
    sort(a + 1, a + n + 1);
    int ans = 0;
    int i = 1;
    for(int j = i; j <= n; j++) {
        int x = mp[a[j]], y = mp[a[i]];
        ans = max(ans, pref[x + 1] - pref[y] - (a[j] - a[i]));
    }
    cout << ans << endl;
}
signed main() {
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...