Submission #1323497

#TimeUsernameProblemLanguageResultExecution timeMemory
1323497rafsanamin2020Art Exhibition (JOI18_art)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll MOD = 1E9 + 7, MX = 1E6 + 2;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n;

  cin >> n;

  vector<pair<ll, ll>> v(n); // size, value;
  vector<ll> p_sum(n + 1, 0);

  ll S = 0;

  for (ll i = 0; i < n; i++)
  {
    cin >> v[i].first;
    cin >> v[i].second;
  }

  sort(v.begin(), v.end());

  for (ll i = 0; i < n; i++)
  {
    p_sum[i] = S;
    S += v[i].second;
  }

  p_sum[n] = S;

  vector<ll> l_max(n, -1E17);
  vector<ll> r_max(n, -1E17);

  l_max[0] = v[0].first;
  r_max[n - 1] = -v[n - 1].first;

  for (ll i = 1; i < n; i++)
  {
    l_max[i] = max(l_max[i - 1], -p_sum[i] + v[i].first);
  }
  for (ll i = n - 2; i > 0; i--)
  {
    r_max[i] = max(r_max[i + 1], -(p_sum[n] - p_sum[i + 1]) - v[i].first);
  }

  // cv(l_max);
  // cv(r_max);

  ll ans = -1E18;

  for (ll i = 0; i < n - 1; i++)
  {
    ans = max(l_max[i] + r_max[i + 1], ans);
  }

  cout << max(p_sum[n] + ans, v[n - 1].second);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...