fork(12) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/x58uJV
language:
C++14 (gcc 8.3)
created:
7 years 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!