Submission #203965

#	Time	Username	Problem	Language	Result	Execution time	Memory
203965		dung11112003	Art Exhibition (JOI18_art)	C++11	100 / 100	300 ms	13560 KiB

art

#include <bits/stdc++.h>

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 5e5 + 10;

int n;
struct pic
{
    ll a, b;
    pic() {}
    pic(ll a, ll b) : a(a), b(b) {}
} art[maxN];
ll prefix[maxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for1(i, n)
    {
        cin >> art[i].a >> art[i].b;
    }
    sort(art + 1, art + n + 1, [](pic x, pic y)
         {
             return x.a < y.a;
         });
    ll res = 0;
    for1(i, n)
    {
        //set with 1 elements
        uax(res, art[i].b);
    }
    for1(i, n)
    {
        prefix[i] = prefix[i - 1] + art[i].b;
    }
    ll kmax = prefix[n] - art[n].a;
    for (int i = n - 1; i; --i)
    {
        uax(res, kmax - prefix[i] + art[i].a + art[i].b);
        uax(kmax, prefix[i] - art[i].a);
    }
    cout << res;
    return 0;
}

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