제출 #1364862

#제출 시각아이디문제언어결과실행 시간메모리
1364862s3yoonparkArt Exhibition (JOI18_art)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h> 
using namespace std; 

void solve() {
    int N; 
    cin >> N; 

    vector<pair<long long,long long>> c(N + 1); 
    vector<long long> pref(N + 1); 

    for (int i = 1; i <= N; i++) {
        cin >> c[i].first >> c[i].second; 
    }

    sort(c.begin() + 1, c.end()); 

    for (int i = 1; i <= N; i++) {
        pref[i] = pref[i - 1] + c[i].second; 
    }

    long long mx = -2E18, ans = 0; 
    for (int i = N; i >= 1; i--) {
        ans = max(ans, mx - (pref[i] - c[i].first - c[i].second)); 
        mx = max(mx, pref[i] - c[i].first);
    } 

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

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    int tests = 1;
    // cin >> tests; 
    while (tests--) solve(); 
    return 0; 
}

/*
sort by increasing sizes 
the optimal answer will be a subarray ... (N ^ 2 is immediate)

oh! 

pref[r] - pref[l - 1] - (A[r] - A[l])
(pref[r] - A[r]) - (pref[l - 1] - A[l])
(pref[r] - A[r]) - (pref[l] - A[l] - B[l])

(pref[r] - A[r]) - (pref[l] - A[l]) + B[l]

ok now this should be easy. 
*/ 
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…