YEZAELP

SMMR-Chi-008: byte coin

Dec 5th, 2021
887
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int N = 1e5 + 10;
  6. int ar[N];
  7. lli dis[N];
  8. int n;
  9.  
  10. lli dfs(int u){
  11.     if(dis[u] != 0) return dis[u];
  12.     dis[u] = 1;
  13.     if(u - 1 >= 1 and ar[u - 1] < ar[u]) dis[u] = max(dis[u], 1 + dfs(u - 1));
  14.     if(u + 1 <= n and ar[u + 1] < ar[u]) dis[u] = max(dis[u], 1 + dfs(u + 1));
  15.     return dis[u];
  16. }
  17.  
  18. int main(){
  19.  
  20.     scanf("%d", &n);
  21.  
  22.     for(int i=1;i<=n;i++)
  23.         scanf("%d", &ar[i]);
  24.  
  25.     for(int i=1;i<=n;i++)
  26.         if(dis[i] == 0) dfs(i);
  27.  
  28.     lli ans = 0;
  29.     for(int i=1;i<=n;i++) ans += dis[i];
  30.  
  31.     cout << ans;
  32.  
  33.     return 0;
  34. }
RAW Paste Data