Submission #1199486

#TimeUsernameProblemLanguageResultExecution timeMemory
1199486A_M_NamdarDivide and conquer (IZhO14_divide)C++20
100 / 100
21 ms7056 KiB
#include <bits/stdc++.h> using namespace std; const long long N = 1e5 + 10; long long n, x[N], d[N], g[N], a[N], ps[N], ps2[N], maxi[N << 2]; void build(long long l, long long r, long long id) { if (r - l == 1) { maxi[id] = ps[l]; return; } long long mid = (l + r) / 2; build(l, mid, id << 1), build(mid, r, id << 1 | 1); maxi[id] = max(maxi[id << 1], maxi[id << 1 | 1]); } long long get(long long l, long long r, long long v, long long id) { if (r - l == 1) return r; long long mid = (l + r) / 2; if (maxi[id << 1 | 1] >= v) return get(mid, r, v, id << 1 | 1); return get(l, mid, v, id << 1); } void input() { cin >> n; for (long long i = 0; i < n; i++) { cin >> x[i] >> g[i] >> d[i]; ps2[i + 1] = ps2[i] + g[i]; if (i > 0) { a[i] = -(x[i] - x[i - 1]) + d[i]; ps[i] = ps[i - 1] + a[i]; } else { a[i] = ps[i] = d[i]; } } } void solve() { build(0, n, 1); long long ans = 0; for (long long i = 0; i < n; i++) { long long tmp = get(0, n, ps[i] - d[i], 1); ans = max(ans, ps2[tmp] - ps2[i]); } cout << ans; } int main() { ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...