Submission #699033

#TimeUsernameProblemLanguageResultExecution timeMemory
699033RichemArt Exhibition (JOI18_art)C++14
100 / 100
684 ms28700 KiB
#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

const int MAX_NOMBRE = 5e5+42;

pair<int, int> tableau[MAX_NOMBRE];
int nbTableau;

int cumul[MAX_NOMBRE] = {0};
int maxI[MAX_NOMBRE] = {0};

signed main() {
    cin >> nbTableau;

    for(int i = 0; i < nbTableau; i++) {
        cin >> tableau[i].first >> tableau[i].second;
    }

    sort(tableau, tableau + nbTableau);

    for(int i = 1; i <= nbTableau; i++) {
        cumul[i] = cumul[i-1] + tableau[i-1].second;
    }

    maxI[0] = tableau[0].first;
    for(int i = 1; i < nbTableau; i++) {
        maxI[i] = max(maxI[i-1], tableau[i].first - cumul[i]);
    }

    int rep = 0;

    for(int i = nbTableau-1; i >= 0; i--) {
        rep = max(rep, maxI[i] + cumul[i+1] - tableau[i].first);
    }

    cout << rep;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...