Submission #757751

#	Time	Username	Problem	Language	Result	Execution time	Memory
757751		JANCARAPAN	Art Exhibition (JOI18_art)	C++17	100 / 100	916 ms	73288 KiB

art

#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;
}

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