Submission #699033

#	Time	Username	Problem	Language	Result	Execution time	Memory
699033		Richem	Art Exhibition (JOI18_art)	C++14	100 / 100	684 ms	28700 KiB

art

#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;
}

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