제출 #1290495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290495		mhaer	Art Exhibition (JOI18_art)	C++20	100 / 100	140 ms	16468 KiB

art

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define vc vector
#define Fin(a) for (auto& i : a)
#define fih ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)

//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast") 
//#pragma GCC target("avx,avx2,fma")
using namespace std;

signed main() {
    fih
    int n;
    cin >> n;
    vc<pii> a(n);
    Fin(a) {
        cin >> i.first;
        cin >> i.second;
    }
    sort(a.begin(), a.end());

    deque<int> start(n);
    deque<int> end(n);

    for (int i = 0;i < n-1;i++) {
        start[i+1] = a[i].second - (a[i+1].first - a[i].first) + start[i];
    }
    // start.push_back(0);

    for (int i = n-1;i >= 1;i--) {
        end[i-1] = a[i].second + (a[i-1].first - a[i].first) + end[i];  
    }
    // end.push_front(0);

    for (int i = 1;i <= n;i++) {
        start[i] = min(start[i-1], start[i]);
    }

    for (int i = n-1;i >= 0;i--) {
        end[i] = min(end[i], end[i+1]);
    }

    // Fin(start) cout << i << " ";
    // cout << "\n";

    // Fin(end) cout << i << " ";
    // cout << "\n";

    int sum = 0;
    int min_ = 1000000000000000000;
    int max_ = -1000000000000000000;
    for (auto& i : a) {
        sum += i.second;
        min_ = min(min_, i.first);
        max_ = max(max_, i.first);
    }

    sum -= (max_ - min_);
    // cout << sum << "\n";

    int v = 0;

    for (int i = 0;i < n;i++) {
        v = max(v, -(start[i] + end[i]));
    }

    cout << sum + v << "\n";

}
 

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