Олимпиада Иннополис, отборочный тур 2, код 1 задач C Barrels

# include <bits/stdc++.h>
# define IoS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
# define Typ long long
  using namespace std;
  struct Roo{
      Typ l, r, a;
      Roo()
      {
          l = r = a = 0;
      }
  }arr[500100];
  Typ n;
  Typ lee[500100], rii[500100];
  map< pair< Typ, int >, Typ > mp_le, mp_ri;
  Typ go_ri(Typ v, int x)
  {
      if(x == n) return min(v, arr[x].a);
      if(v <= arr[x].a) return v;
      long long ans = mp_ri[{v, x}];
      if(ans != 0) return ans;
      ans = arr[x].a + go_ri(min(v - arr[x].a, arr[x].r), x + 1);
      mp_ri[{v, x}] = ans;
      return ans;
  }
  Typ go_le(Typ v, int x)
  {
      if(x == 1) return min(v, arr[x].a);
      if(v < arr[x].a) return v;
      long long ans = mp_le[{v, x}];
      if(ans != 0) return ans;
      ans = arr[x].a + go_le(min(v - arr[x].a, arr[x].l), x - 1);
      mp_le[{v, x}] = ans;
      return ans;
  }
  int main()
  {
      IoS;
      long long i, ans, s, dx;
      cin >> n;
      for(i = 1; i <= n; i++){
        cin >> arr[i].l >> arr[i].r >> arr[i].a;
        if(i == 1) lee[i] = arr[i].a;
        else lee[i] = arr[i].a + arr[i - 1].a;
        if(1 < i) rii[i - 1] = arr[i - 1].a + arr[i].a;
        if(i == n) rii[n] = arr[n].a;
      }
      if(n == 1) cout << arr[1].a;
      else {
          for(i = 2; i <= n; i++){
            lee[i] += min(arr[i].l - arr[i - 1].a, lee[i - 1] - arr[i - 1].a);
          }
          ans = max(arr[1].a + go_ri(arr[1].r, 2), arr[n].a + go_le(arr[n].l, n - 1));
          for(i = n - 1; i >= 1; i--){
            rii[i] += min(arr[i].r - arr[i + 1].a, rii[i + 1] - arr[i + 1].a);
            ans = max(ans, lee[i] + rii[i] - arr[i].a);
          }
          cout << ans;
      }
      return 0;
  }
/**
*/