fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod=998244353;
  5. const ll INF = -10000000000000;
  6.  
  7. void solve() {
  8.     ll n;
  9.     cin >> n;
  10.     vector<ll> a(n+1);
  11.     for(ll i=1;i<=n;i++) cin >> a[i];
  12.     unordered_map<ll,vector<ll>> mp;
  13.     for(ll i=2;i<=n;i++){
  14.         ll need = a[i]+i-1;
  15.         mp[need].push_back(i);
  16.     }
  17.     for(auto &vc : mp){
  18.         auto &ve = vc.second;
  19.         sort(ve.begin(),ve.end());
  20.     }
  21.     ll ans = n;
  22.     auto it=mp.find(n);
  23.     if(it==mp.end()) {cout << n << '\n';return;}
  24.     for(int i :it->second){
  25.         ll best = n;
  26.         ll curr = n;
  27.         ll j=i;
  28.         while(true){
  29.             curr+=j-1;
  30.             best=max(best,curr);
  31.  
  32.             auto ite = mp.find(curr);
  33.             if(ite==mp.end()) break;
  34.  
  35.             auto &ve = ite->second;
  36.             j=ve.back();
  37.         }
  38.         ans=max(ans,best);
  39.     }
  40.     cout << ans << '\n';
  41. }
  42.  
  43. int main(){ 
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.  
  47.     int t;
  48.     cin >> t;
  49.     while (t--) solve();
  50.  
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
4
5
2 4 6 2 5
5
5 4 4 5 1
4
6 8 2 3
1
1
stdout 
10
11
10
1
https://ideone.com/peY7sx
language:
C++ (gcc 8.3)
created:
8 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!