Advertisement
Guest User

Untitled

a guest
Jan 18th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.61 KB | None | 0 0
  1. // DP practice
  2. // 455A --- codeforces
  3. #include <iostream>
  4. #include <stdio.h>
  5. #include <cstring>
  6. using namespace std;
  7. const int N = 1000010;
  8. long long int dp[N];
  9. long long int cnt[N];
  10. int main()
  11. {
  12. int iT;
  13. int iNum,iLarge;
  14. int i,j;
  15. cin >> iT;
  16. memset(cnt,0,sizeof(cnt));
  17. iLarge = 0;
  18. for ( i=0 ; i<iT ; i++ )   
  19.     {
  20.     cin >> iNum;
  21.     // count number appear times
  22.     cnt [iNum]++;
  23.     // store the largest number to reduce run time
  24.     if ( iNum>iLarge )
  25.         iLarge = iNum;
  26.     }
  27. dp[0] = 0;
  28. dp[1] = cnt[1];
  29. for ( j=2 ; j<=iLarge ; j++ )
  30.     dp[j] = max(dp[j-1],dp[j-2] + (cnt[j]*j)); 
  31.        
  32. cout << dp[j-1] << endl;   
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement