This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << '\n'; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef imtiyazrasool92
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
void run_case() {
int N;
cin >> N;
vector<array<int64_t, 2>> A(N);
for (auto &[x, y] : A)
cin >> x >> y;
sort(A.begin(), A.end());
priority_queue<int64_t> Q;
Q.push((A[1][0] - A[0][0]) - A[0][1]);
int64_t answer = A[0][1];
int64_t prefix = A[0][1];
for (int i = 1; i < N; i++) {
prefix += A[i][1];
prefix -= abs(A[i][0] - A[i - 1][0]);
answer = max<int64_t>(answer, prefix);
answer = max<int64_t>(answer, prefix + Q.top());
if (i + 1 < N) {
Q.push(-prefix);
}
}
cout << answer;
}
int32_t main() {
ios::sync_with_stdio(false);
#ifndef imtiyazrasool92
cin.tie(nullptr);
#endif
int tests = 1;
// cin >> tests;
while (tests--) {
run_case();
cout << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |