nguyenthieukhang

262144 USACO

Sep 21st, 2020
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int mxn = 1e6+10;
  5. const int inf = 1e9;
  6. int a[mxn], dp[mxn][70];
  7.  
  8. int main() {
  9.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10.     freopen("262144.in", "r", stdin);
  11.     freopen("262144.out", "w", stdout);
  12.  
  13.     int n; cin>>n;
  14.     for(int i=0; i<n; i++) cin>>a[i];
  15.  
  16.     for(int i=0; i<n+3; i++) for(int j=0; j<70; j++) dp[i][j] = -1;
  17.     for(int i=0; i<n; i++) dp[i][a[i]] = i;
  18.  
  19.     for(int i=n-2; i>=0; i--) {
  20.         for(int j=1; j<70; j++) {
  21.             if(dp[i][j-1]!=-1) dp[i][j] = dp[dp[i][j-1]+1][j-1];
  22.         }
  23.     }
  24.  
  25.     int mx = 0;
  26.     for(int i=0; i<n; i++) for(int j=1; j<70; j++) if(dp[i][j]!=-1) mx = max(mx, j);
  27.  
  28.     cout << mx << '\n';
  29.  
  30.     return 0;
  31. }
RAW Paste Data