Submission #757751

#TimeUsernameProblemLanguageResultExecution timeMemory
757751JANCARAPANArt Exhibition (JOI18_art)C++17
100 / 100
916 ms73288 KiB
#include <bits/stdc++.h>
using namespace std;  
#define int long long
#define fi first
#define se second
#define sz(a) (long long) a.size()
#define endl '\n'

const long long INF = 1e18, MOD = 1e9+7;


void test_case() {
  int n;
  cin >> n;
  
  vector<int> a;
  map<int,int> mp;
  for (int i = 0; i < n; i++) {
    int s, v;
    cin >> s >> v;
    if (!mp.count(s)) {
      a.push_back(s);
    }
    mp[s] += v;
  }
  sort(a.begin(), a.end());
  
  set<pair<int,int>> s;
  
  vector<int> value(sz(a));
  
  int cur = 0;
  for (int i = 0; i < sz(a); i++) {
    cur += mp[a[i]];
    s.insert({cur - a[i], i});
    value[i] = cur - a[i];
  }
  
  int ans = 0;
  for (int i = 0; i < sz(a); i++) {
    ans = max(ans, (*s.rbegin()).fi + a[i] - (i? value[i - 1] + a[i - 1] : 0));
    auto it = s.find({value[i], i});
    assert(it != s.end());
    s.erase(it);
  }
  cout << ans << endl;
}
 
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    test_case();
  }
  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...