#include <bits/stdc++.h>
// #ifndef ONLINE_JUDGE
// #include "debug.cpp"
// #else
// #define debug(...)
// #define debugArr(...)
// #endif
#pragma region
#define int long long
#define vec vector
#define vlong vec<long>
#define vint vec<int>
#define vchar vec<char>
#define vbool vec<bool>
#define vvint vec<vint>
#define vstr vec<string>
#define vstring vstr
#define vpint vec<pair<int, int> >
#define CININT(n) INTCIN(n);
#define INTCIN(n) int n; cin >> n;
#define INTCINVINTCIN(a, n) INTCIN(n); vint a(n); CINV(a, n);
#define TWOVECS(a, b, n) INTCIN(n); vint a(n), b(n); CINV(a, n) CINV (b, n);
#define TWOCOLS(a, b, n) INTCIN(n); vint a(n), b(n); CINVV(a, b, n);
#define ICVK(n, k, a) CININT(n); CININT(k); vint a(n); CINV(a, n);
#define ICVK1(n, k, a) ICVK(n, k, a)
#define ICVK2(n, k, h, a) CININT(n); CININT(k); CININT(h); vint a(n); CINV(a, n);
#define ICVK3(n, k, h, m, a) CININT(n); CININT(k); CININT(h); CININT(m); vint a(n); CINV(a, n);
#define CIN(n) cin >> n;
#define COUT(n) cout << n;
#define CINV(a, n) for (int i = 0; i < n; i++) {cin >> a[i];}
#define CINVV(a, b, n) for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}
#define COUTV(a, n) for (int i = 0; i < n; i++) {cout << a[i] << " ";}
#define COUTVV(a, b, n) for (int i = 0; i < n; i++) {cout << a[i] << " " << b[i] << "\n";}
#define NOSPACE(a, n) for (int i = 0;i < n;i++) {cout << a[i];}
#define ENDL cout << "\n";
#define SORT(a) sort(a.begin(), a.end());
#define REVERSE(a) reverse(a.begin(), a.end());
#define HAS(theset, num) ((theset.find((num)) != (theset.end())))
#define FOR(i, n) for (int i = 0; i < n; i++)
#define FOR1(i, n) for (int i = 1; i < n; i++)
#define YES if (true) {cout << "YES"; return;}
#define NO if (true) {cout << "NO"; return;}
#define Yes if (true) {cout << "Yes"; return;}
#define No if (true) {cout << "No"; return;}
#define IMPOS if (true) {cout << "Impossible"; return;}
#define IMPOSS IMPOS
#define SP " "
#define NEWLINE "\n"
#define Q int q;cin>>q;while(q--)
#pragma endregion
using namespace std;
void pre() {}
// you can do this!
const bool DO_ENDL = true;
const bool MULTI_T = false; // :skull: dont forgorr me!!
void solve() {
int n;
cin >> n;
vec<pair<int, int> > a(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a[i] = {x, y};
}
SORT(a);
vint val_pfx(n+1);
for (int i = 1; i <= n; i++) {
val_pfx[i] = a[i-1].second + val_pfx[i-1];
}
// naive
int ans = 0;
// for (int i = 0; i < n; i++) {
// for (int j = i; j < n; j++) {
// ans = max(ans,
// -(a[j].first - a[i].first) + val_pfx[j+1] - val_pfx[i]
// );
// }
// }
int bestj = 0;
for (int i = 0; i < n; i++) {
int oldi = i;
for (int j = max(bestj, i); j < n; j++) {
int newval = -(a[j].first - a[i].first) + val_pfx[j+1] - val_pfx[i];
int oldval = -(a[bestj].first - a[i].first) + val_pfx[bestj+1] - val_pfx[i];
ans = max(ans,
newval
);
if (newval > oldval) bestj = j;
}
int besti = i;
for (; i <= bestj; i++) {
int newval = -(a[bestj].first - a[i].first) + val_pfx[bestj+1] - val_pfx[i];
int oldval = -(a[bestj].first - a[besti].first) + val_pfx[bestj+1] - val_pfx[besti];
ans = max(ans,
newval
);
if (newval > oldval) {
besti = i;
}
}
i = max(i-5, oldi+1);
// i = besti;
}
cout << ans;
}
signed main() {
pre();
if (not MULTI_T)
{solve();
return 0;}
CININT(t);
while (t--) {
solve();
if (DO_ENDL)
ENDL;
}
}
Compilation message
art.cpp:10: warning: ignoring '#pragma region ' [-Wunknown-pragmas]
10 | #pragma region
|
art.cpp:63: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
63 | #pragma endregion
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
