Submission #1169187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169187		vyaduct	Art Exhibition (JOI18_art)	C++20	0 / 100	0 ms	320 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define all(c) (c).begin(), (c).end()

void solve(){
  int n; cin>>n;
  vector<pair<ll, ll>> A(n);
  vector<ll> pref(n+1);
  for (int i=0;i<n;i++){
    cin>>A[i].F>>A[i].S;
  }
    
  sort(all(A));
  for (int i=0;i<n;i++) pref[i+1] = pref[i] + A[i].S;

  int l=0, r=n-1;
  ll best=0;
  while(l<r){
    ll v = pref[r+1] - pref[l] - (A[r].F - A[l].F);
    best = max(best, v);
    ll left = pref[r] - pref[l+1] - (A[r].F - A[l+1].F);
    ll right = pref[r] - pref[l] - (A[r-1].F - A[l].F);
    if (left < best && right < best) break;
    if (left > right || right < best){
      l++;
    } else {
      r--;
    }
  }
  cout << best << endl;
}

int main(){
  solve();
  return 0;
}

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