fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <cassert>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef pair<int, int> ii;
  7. typedef pair<ll, ll> pll;
  8. typedef pair<int, ll> pil;
  9. typedef vector<int> vi;
  10. typedef unsigned long long ull;
  11. typedef double db;
  12. typedef long double ld;
  13. #define fi first
  14. #define se second
  15. #define vt vector
  16. #define all(x) x.begin(), x.end()
  17. #define popcnt __builtin_popcount
  18. #define hibit(x) 31 - __builtin_clz(x)
  19.  
  20. constexpr int N = 2e5 + 1;
  21.  
  22. int x[N], y[N], c[N];
  23. ll a[N], dp[N], st[N << 2], lz[N << 2];
  24.  
  25. void build(int u, int l, int r) {
  26.     if (l == r) {
  27.         st[u] = -a[l];
  28.         return;
  29.     }
  30.     const int mid = l + r >> 1, c1 = u << 1, c2 = c1 | 1;
  31.     build(c1, l, mid);
  32.     build(c2, mid + 1, r);
  33.     st[u] = max(st[c1], st[c2]);
  34. }
  35.  
  36. inline void push(int u, int c1, int c2) {
  37.     if (lz[u] != lz[c1]) {
  38.         st[c1] += lz[u] - lz[c1];
  39.         lz[c1] = lz[u];
  40.     }
  41.     if (lz[u] != lz[c2]) {
  42.         st[c2] += lz[u] - lz[c2];
  43.         lz[c2] = lz[u];
  44.     }
  45. }
  46.  
  47. void upd(int u, int l, int r, int ql, ll v) {
  48.     if (ql > r) return;
  49.     if (ql <= l) {
  50.         if (lz[u] < v) {
  51.             st[u] += v - lz[u];
  52.             lz[u] = v;
  53.         }
  54.         return;
  55.     }
  56.     const int mid = l + r >> 1, c1 = u << 1, c2 = c1 | 1;
  57.     push(u, c1, c2);
  58.     upd(c1, l, mid, ql, v);
  59.     upd(c2, mid + 1, r, ql, v);
  60. }
  61.  
  62. ll query(int u, int l, int r, int ql, int qr) {
  63.     if (ql > r || qr < l) return 0;
  64.     if (ql <= l && r <= qr) return st[u];
  65.     const int mid = l + r >> 1, c1 = u << c1, c2 = c1 | 1;
  66.     push(u, c1, c2);
  67.     return max(query(c1, l, mid, ql, qr), query(c2, mid + 1, r, ql, qr));
  68. }
  69.  
  70. int main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.     int n;
  74.     cin >> n;
  75.     for (int i = 1; i <= n; ++i) {
  76.         cin >> a[i];
  77.         a[i] += a[i - 1];
  78.     }
  79.     for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i] >> c[i];
  80.     build(1, 0, n);
  81.     for (int i = 1; i <= n; ++i) {
  82.         dp[i] = a[i] - c[i] + query(1, 0, n, i - x[i], i - y[i]);
  83.         upd(1, 0, n, i, dp[i]);
  84.     }
  85.     cout << *max_element(dp + 1, dp + n + 1);
  86. }
Success #stdin #stdout 0.01s 7748KB
comments (?)
stdin
copy 
5
4 -1 5 6 -2
1 1 3
1 2 2
2 3 10
1 4 3
1 1 1
stdout
copy 
11
https://ideone.com/P7P3zI
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!