#include <bits/stdc++.h>
#define FOR(i,x,n) for(int i=x; i<n; i++)
#define F0R(i,n) FOR(i,0,n)
#define ROF(i,x,n) for(int i=n-1; i>=x; i--)
#define R0F(i,n) ROF(i,0,n)
#define WTF cout << "WTF" << endl
#define IOS ios::sync_with_stdio(false); cin.tie(0)
#define F first
#define S second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
const int MAXN = 2e5 + 7;
const int ALPHA = 27;
const LL INF = 1e16 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;
struct Mine {
LL pt, gd, eg;
} ns[MAXN];
int n;
int solve(int l, int r) {
if (l == r) return ns[l].gd;
int mid = (l + r) >> 1;
LL ret = max(solve(l, mid), solve(mid + 1, r));
//cout << "solving for : " << l << ' ' << r << endl;
VPLL lf, rt;
LL gsum = 0, esum = 0;
ROF(i, l, mid + 1) {
gsum += ns[i].gd;
esum += ns[i].eg;
lf.pb({esum - (ns[mid].pt - ns[i].pt), gsum});
}
gsum = 0, esum = 0;
FOR(i, mid + 1, r + 1) {
gsum += ns[i].gd;
esum += ns[i].eg;
rt.pb({esum - (ns[i].pt - ns[mid].pt), gsum});
}
/*
for(auto [id, val] : lf) cout << "(" << id << ", " << val << ") ";
cout << endl;
for(auto [id, val] : rt) cout << "(" << id << ", " << val << ") ";
cout << endl;
*/
sort(ALL(lf));
sort(RALL(rt));
LL lmx = 0, rmx = -INF, rptr = 0;
for(auto [weight, gold] : lf) {
lmx = max(lmx, (LL)gold);
while(rptr < rt.size() && weight + rt[rptr].F >= 0) {
rmx = max(rmx, rt[rptr].S);
rptr++;
}
ret = max(ret, lmx + rmx);
}
return ret;
}
int main() {
IOS;
cin >> n;
F0R(i, n) cin >> ns[i].pt >> ns[i].gd >> ns[i].eg;
cout << solve(0, n - 1);
}
Compilation message
divide.cpp: In function 'int solve(int, int)':
divide.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for(auto [weight, gold] : lf) {
| ^
divide.cpp:80:20: warning: comparison of integer expressions of different signedness: 'LL' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | while(rptr < rt.size() && weight + rt[rptr].F >= 0) {
| ~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Incorrect |
0 ms |
324 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |