Submission #1258347

#TimeUsernameProblemLanguageResultExecution timeMemory
1258347meisean2009Art Exhibition (JOI18_art)C++20
0 / 100
0 ms320 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...