제출 #1258347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258347		meisean2009	Art Exhibition (JOI18_art)	C++20	0 / 100	0 ms	320 KiB

art

#include <bits/stdc++.h>
#define int long long 
using namespace std;
typedef pair<int,int> p;
#define f first 
#define s second 

signed main(){
    int n;
    cin >> n;
    vector<p> artworks(n);
    
    for (int i = 0; i < n; i++){
        cin >> artworks[i].f >> artworks[i].s;  // size, value
    }
    
    sort(artworks.begin(), artworks.end());  // sort by size
    
    int ans = 0;
    int prefix_sum = 0;
    int min_prefix_minus_first = 0;  // minimum of (prefix_sum - first_size)
    
    for (int i = 0; i < n; i++){
        int size = artworks[i].f;
        int value = artworks[i].s;
        
        prefix_sum += value;
        
        // Current answer if we end at position i
        // S - (Amax - Amin) = prefix_sum - (current_size - min_size_in_range)
        // We want to maximize: prefix_sum - current_size + min_size_in_range
        // This equals: prefix_sum - current_size - min(prefix_sum_at_start - size_at_start)
        ans = max(ans, prefix_sum - size - min_prefix_minus_first);
        
        // Update minimum for next iteration
        min_prefix_minus_first = min(min_prefix_minus_first, prefix_sum - size);
    }
    
    cout << ans << endl;
    return 0;
}

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