//#include <bits/stdc++.h>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ll = long long;
#define int long long
const int N = 5e5 + 7;
const int M = 1e16 + 7;
struct custom_hash { //unordered_map<long long, int, custom_hash> safe_map; gp_hash_table<long long, int, custom_hash> safe_hash_table;
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
int binpow(int a, int n, int m) {
int res = 1;
while (n) {
if (n & 1) res = res * a % m;
a = a * a % m;
n >>= 1;
}
return res;
}
/*inline void factorials(int n) {
f[0] = 1;
for(int i = 1; i <= n; i++) {
f[i] = (f[i - 1] * i) % M;
}
invf[n] = binpow(f[n], M - 2, M);
for(int i = n - 1; i >= 0; i--) {
invf[i] = (invf[i + 1] * (i + 1)) % M;
}
}
inline int cnk(int n, int k) {
if(k > n) {
return 0;
}
return (((f[n] * invf[n - k]) % M) * invf[k]) % M;
} */
pair<int, int> a[N];
int p[N];
inline void Solve() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) {
p[i] = p[i - 1] + a[i].second;
}
int mx = 0, ans = 0;
for(int i = 1; i <= n; i++) {
mx = max(mx, a[i].first - p[i - 1]);
ans = max(ans, p[i] - a[i].first + mx);
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
//cout << '\n' << '\n';
while(t--) {
Solve();
}
return 0;
}
/*
Special cases n = 1 or just 1?
u r using unsigned long long which can't carry negative values?
what if u r doing the same thing n times, it may cause the TL
make sure that the size of your massives, vectors are enough
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 43 |
Correct |
2 ms |
2520 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 46 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 49 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 43 |
Correct |
2 ms |
2520 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 46 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 49 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 52 |
Correct |
111 ms |
12116 KB |
Output is correct |
| 53 |
Correct |
113 ms |
11988 KB |
Output is correct |
| 54 |
Correct |
112 ms |
12116 KB |
Output is correct |
| 55 |
Correct |
112 ms |
12116 KB |
Output is correct |
| 56 |
Correct |
123 ms |
12112 KB |
Output is correct |
| 57 |
Correct |
134 ms |
12128 KB |
Output is correct |
| 58 |
Correct |
113 ms |
12116 KB |
Output is correct |
| 59 |
Correct |
118 ms |
12116 KB |
Output is correct |
| 60 |
Correct |
114 ms |
11992 KB |
Output is correct |
| 61 |
Correct |
117 ms |
12068 KB |
Output is correct |
| 62 |
Correct |
134 ms |
12028 KB |
Output is correct |
| 63 |
Correct |
115 ms |
11972 KB |
Output is correct |
| 64 |
Correct |
123 ms |
11972 KB |
Output is correct |
| 65 |
Correct |
119 ms |
11968 KB |
Output is correct |
| 66 |
Correct |
114 ms |
11988 KB |
Output is correct |
| 67 |
Correct |
126 ms |
11976 KB |
Output is correct |
| 68 |
Correct |
124 ms |
11980 KB |
Output is correct |
