Submission #966094

#	Time	Username	Problem	Language	Result	Execution time	Memory
966094		MercubytheFirst	Art Exhibition (JOI18_art)	C++17	100 / 100	267 ms	68204 KiB

art

#include <bits/stdc++.h>
using ll = long long;
#define pb push_back
using namespace std;
#define CDIV(a, b) ((((a) - (1)) / (b)) + 1)
const ll inf = 1e9 + 37;



template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);

// using __int128_t = long long;

void solve() { 
  ll tempn;
  cin >> tempn;
  __int128_t n = tempn;
  vector<pair<__int128_t, __int128_t> > v(n + 1);
  vector<__int128_t> pref(n + 1);
  for(__int128_t i = 1; i <= n; ++i) {
    ll a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  sort(v.begin() + 1, v.end());
  for(__int128_t i = 1; i <= n; ++i){
    pref[i] = pref[i - 1] + v[i].second;
  }
  // cout << v << endl << pref << endl;
  set<__int128_t> s;
  __int128_t ans = 0;
  for(__int128_t i = 1; i <= n; ++i) {
    s.insert(v[i].first - pref[i - 1]);
    ans = max(ans, pref[i] - v[i].first + *s.rbegin());
  }
  cout << (ll)ans << endl;
}

signed main() {
  // #ifndef ONLINE_JUDGE
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // #endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // signed t = 0; cin >> t; while(t --> 0) 
    solve();
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << '[';
  for(size_t i = 0; i < N; ++i) {
    os << a[i] << " ";
  }
  os << "]";
  return os;
}

template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << " ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}
 
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

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