fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void fileIO()
  5. {
  6.     ios_base::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     cout.tie(nullptr);
  9. #ifndef ONLINE_JUDGE
  10.     freopen("input.txt", "r", stdin);
  11.     freopen("output.txt", "w", stdout);
  12. #endif
  13. }
  14.  
  15. struct SparseTable
  16. {
  17.     vector<vector<int>> table;
  18.     vector<int> lg;
  19.     vector<int> v;
  20.     SparseTable(int n, vector<int> &v) : v(v)
  21.     {
  22.         lg = vector<int>(n + 1);
  23.         lg[1] = 0;
  24.         for (int i = 2; i <= n; i++)
  25.             lg[i] = lg[i / 2] + 1;
  26.         table = vector<vector<int>>(n + 2, vector<int>(lg[n] + 2));
  27.         for (int i = 0; i < n; i++)
  28.             table[i][0] = i;
  29.         for (int j = 1; j <= lg[n]; j++)
  30.         {
  31.             for (int i = 0; i + (1 << (j - 1)) < n; i++)
  32.             {
  33.                 if (v[table[i][j - 1]] <= v[table[i + (1 << (j - 1))][j - 1]])
  34.                     table[i][j] = table[i][j - 1];
  35.                 else
  36.                     table[i][j] = table[i + (1 << (j - 1))][j - 1];
  37.                 // table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  38.             }
  39.         }
  40.     }
  41.     int query(int l, int r)
  42.     {
  43.         int g = lg[r - l + 1];
  44.         if (v[table[l][g]] <= v[table[r - (1 << g) + 1][g]])
  45.             return table[l][g];
  46.  
  47.         return table[r - (1 << g) + 1][g];
  48.     }
  49. };
  50.  
  51. long long sum(int x)
  52. {
  53.     return x * 1ll * (x + 1) / 2;
  54. }
  55.  
  56. void Striker()
  57. {
  58.     int n;
  59.     cin >> n;
  60.     int a[n];
  61.     vector<int> v(n);
  62.     for (int i = 0; i < n; i++)
  63.     {
  64.         cin >> a[i];
  65.         v[i] = a[i];
  66.     }
  67.     SparseTable table(n, v);
  68.     long long dp[n + 2]{};
  69.     for (int i = n - 1; ~i; i--)
  70.     {
  71.         int st = i, en = min(n - 1, a[i] + i), idx = i;
  72.         // cout << table.query(0, n - 1) << ' ';
  73.         while (st <= en)
  74.         {
  75.             int mid = st + en >> 1;
  76.             auto tmp = table.query(i, mid);
  77.  
  78.             if (v[tmp] >= a[i] - (tmp - i)) // min value in range should be less than min value I will effect
  79.             {
  80.                 idx = mid;
  81.                 st = mid + 1;
  82.             }
  83.             else
  84.             {
  85.                 en = mid - 1;
  86.             }
  87.         }
  88.         // cout << idx << '\n';
  89.         int sz = idx - i + 1;
  90.         dp[i] = sum(a[i]) - sum(a[i] - sz);
  91.         if (idx < min(n - 1, a[i] + i))
  92.             dp[i] += dp[idx + 1];
  93.     }
  94.     cout << *max_element(dp, dp + n) << '\n';
  95. }
  96.  
  97. signed main()
  98. {
  99.     fileIO();
  100.     int _t = 1;
  101.     cin >> _t;
  102.     for (int i = 0; i < _t; ++i)
  103.     {
  104.         Striker();
  105.     }
  106. }
Success #stdin #stdout 0.01s 7292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2147479976
https://ideone.com/LPBIOT
language:
C++ (gcc 8.3)
created:
4 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!