Submission #1115359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115359		staszic_ojuz	Art Exhibition (JOI18_art)	C++17	100 / 100	141 ms	36432 KiB

art

#include<bits/stdc++.h>
using namespace std;
using i64 = int64_t;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    i64 N;
    cin >> N;

    i64 mi = INT64_MAX, ma = 0, suma = 0;;
    vector<pair<i64, i64>> table(N);
    for (i64 i = 0; i < N; i++)
    {
        cin >> table[i].first >> table[i].second;
        suma += table[i].second;
        mi = min(mi, table[i].first);
        ma = max(ma, table[i].first);
    }

    sort(table.begin(), table.end());

    vector<pair<i64, i64>> pra(N);
    vector<pair<i64, i64>> lew(N);
    for (i64 i = 1; i < N; i++)
    {
        pra[i].first = pra[i - 1].first + (table[i].first - table[i - 1].first) - table[i - 1].second;
        pra[i].second = max(pra[i - 1].second, pra[i].first);
        //cout << pra[i].first << " : " << pra[i].second << "\n";
    }
    //cout << "\n";
    for (i64 i = N - 2; i >= 0; i--)
    {
        lew[i].first = lew[i + 1].first + (table[i + 1].first - table[i].first) - table[i + 1].second;
        lew[i].second = max(lew[i + 1].second, lew[i].first);
        //cout << lew[i].first << " : " << lew[i].second << "\n";
    }

    i64 maxx = 0;
    for (i64 i = 0; i < N; i++)
    {
        maxx = max(maxx, pra[i].second + lew[i].second);
    }
    cout << suma + mi + maxx - ma << "\n";

    return 0;
}

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