fork(10) download
  1. #include <cmath>
  2. #include <bits/stdc++.h>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8. #define MAX 1000000
  9. typedef long long ll;
  10. long long dp[MAX];
  11. int arr[MAX];
  12. int main() {
  13. /* Enter your code here. Read input from STDIN. Print output to STDOUT */
  14. memset(arr,0,sizeof(arr));
  15. int n;
  16. cin>>n;
  17. for(int i=0;i<n;i++)
  18. cin>>arr[i];
  19. dp[0]=1;
  20. for(int i=1;i<n;i++){
  21. if(arr[i]>arr[i-1])
  22. dp[i]=dp[i-1]+1; // if right person has more rating he gets extra candy
  23. else if(arr[i]<=arr[i-1])
  24. dp[i]=1; // else he gets 1 candy
  25. }
  26. /* This maintains the condition, if left person has higher rating then he will be awarded one more candy */
  27. /* max is used because if mid element has max rating his candy should be greater than both left and rights guys check my comment in codechef*/
  28. for(int i=n-2;i>=0;i--){
  29. if(arr[i]>arr[i+1])
  30. dp[i]=max(dp[i],dp[i+1]+1);
  31. }
  32. ll sum=0;
  33. for(int i=0;i<n;i++){
  34. sum+=dp[i];
  35. // cout<<dp[i]<<endl;
  36. }
  37. cout<<sum<<endl;
  38. return 0;
  39. }
  40.  
Success #stdin #stdout 0s 26944KB
stdin
Standard input is empty
stdout
0