Submission #651437

#	Time	Username	Problem	Language	Result	Execution time	Memory
651437		pauloamed	Art Exhibition (JOI18_art)	C++17	100 / 100	583 ms	24744 KiB

art

#include<bits/stdc++.h>
using namespace std;

#define int long long

int32_t main(){
  int n; cin >> n;
  vector<pair<int,int>> v(n);
  for(auto &[a, b] : v) cin >> a >> b;
  sort(v.begin(), v.end());

  vector<int> sum(n);
  for(int i = 0; i < n; ++i){
    sum[i] = v[i].second;
    if(i > 0) sum[i] += sum[i - 1];
  }

  int best_ans = LLONG_MIN;
  int max_inv = LLONG_MIN;
  for(int i = 0; i < n; ++i){
    int inv_a = sum[i] - v[i].first;
    int inv_b = v[i].first - ((i - 1 < 0)? 0 : sum[i - 1]);

    max_inv = max(max_inv, inv_b);

    best_ans = max(best_ans, inv_a + max_inv);
  }
  cout << best_ans << "\n";
}

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