Submission #711954

#	Time	Username	Problem	Language	Result	Execution time	Memory
711954		thimote75	Art Exhibition (JOI18_art)	C++14	100 / 100	993 ms	52464 KiB

art

#include <bits/stdc++.h>

using namespace std;

#define num long long
#define ndata vector<num>

struct VBO {
    map<num, num> sv_by_s;

    num _get_e(num size) {
        auto u = sv_by_s.find(size);
        if (u == sv_by_s.end()) return 0;

        num res = (*u).second;
        sv_by_s.erase(size);
        return res;
    }
    void insert (num size, num value) {
        num old = _get_e(size);

        sv_by_s.insert({ size, old + value });
    }
};

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

    VBO data;
    for (int iA = 0; iA < nbArt; iA ++) {
        num a, b;
        cin >> a >> b;

        data.insert(a, b);
    }

    ndata size;
    ndata value;
    for (auto d : data.sv_by_s) {
        size .push_back(d.first);
        value.push_back(d.second);
    }

    nbArt = size.size();

    num max_v = 0;
    num sum_v = 0;
    num max_a = 0;
    
    for (int iA = 0; iA < nbArt; iA ++) {
        max_v = max(max_v, size[iA] - sum_v);
        num answer = sum_v + value[iA] - size[iA] + max_v;
        max_a = max(max_a, answer);
        
        sum_v += value[iA];
    }

    cout << max_a;
}

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