제출 #791848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791848		Boomyday	Art Exhibition (JOI18_art)	C++17	100 / 100	167 ms	42028 KiB

art

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second



#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!


int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    vector<pair<ll, ll>> arts;
    F0R(i, N){
        ll a, b; cin >> a >> b;
        arts.pb({a,b});
    }
    sort(all(arts));
    vl A,B;
    for(auto&[a, b]:arts){
        A.pb(a); B.pb(b);
    }
    vl prefs = {0};
    F0R(i, N) prefs.pb(prefs.back()+B[i]);
    vl prefs_orig(all(prefs));
    F0R(i, N){
        prefs[i+1] -= A[i];
    }
    vl suffix_maxs(N+1, -INF);
    suffix_maxs.back() = prefs.back();
    for(int i=N-1;i>-1;--i){
        suffix_maxs[i] = max(suffix_maxs[i+1],prefs[i]);
    }
    ll mx = *max_element(all(B));
    F0R(st, N){
        ll bestmx = suffix_maxs[st+1];
        mx = max(mx, bestmx-prefs_orig[st]+A[st]);
    }
    cout <<mx << endl;


}

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