제출 #627144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
627144		boris_mihov	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	340 KiB

art

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>

typedef long long llong;
const int MAXN = 500000 + 10;
const llong INF = 1e16;

int n;
llong idx[MAXN];
llong a[MAXN], b[MAXN];
llong a2[MAXN], b2[MAXN];
llong prefixB[MAXN];
void solve()
{
    std::iota(idx + 1, idx + 1 + n, 1);
    std::sort(idx + 1, idx + 1 + n, [&](int x, int y)
    {
        return std::make_pair(a[x], b[x]) < std::make_pair(a[y], b[y]);
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        a2[i] = a[idx[i]];
        b2[i] = b[idx[i]];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = a2[i];
        b[i] = b2[i];
    }

    llong ans = -INF, max = -INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        prefixB[i] = prefixB[i-1] + b[i];
        ans = std::max(ans, prefixB[i] - a[i] + max);
        max = std::max(max, a[i] - prefixB[i-1]);
    }

    std::cout << ans << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i] >> b[i];
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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