Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1.     #include <iostream>
  2.     #include <bits/stdc++.h>
  3.     typedef long long ll;
  4.     using namespace std;
  5.     ll n,k;
  6.     vector <ll> v;
  7.     vector <pair <ll,ll> > ar;
  8.     ll dp[100005];
  9.     ll solve(ll i,ll elements){
  10.         ll temp1,temp2,temp3,c1 = 0,c2 = 0, found = 0;
  11.         if(elements== 0) return 0;
  12.         if(i>=ar.size()) return -1e17;
  13.         if(dp[i] +1) return dp[i];
  14.         if(i!=0 ) {temp1 = ar[i-1].second; if(ar[i].first-ar[i-1].first==1){elements-=temp1;ar[i-1].second= 0;}}
  15.         if(i!=ar.size()-1){temp2=ar[i+1].second;if(ar[i+1].first-ar[i].first==1){elements-=temp2;ar[i+1].second = 0; found = 1;}}
  16.         temp3 = ar[i].second;
  17.         ar[i].second = 0;
  18.         if(found){
  19.         c1 = solve(i+2,elements-temp3)+ar[i].first*temp3;
  20.         } else {
  21.         c1 = solve(i+1,elements-temp3)+ar[i].first*temp3;
  22.         }
  23.         ar[i].second = temp3;
  24.         if(i!=0) { if(ar[i].first-ar[i-1].first==1){elements+=temp1;ar[i-1].second= temp1;}}
  25.         if(i!=ar.size()-1){if(ar[i+1].first-ar[i].first==1){elements+=temp2;ar[i+1].second = temp2;}}
  26.         c2 = solve(i+1,elements);
  27.         return dp[i] = max(c1,c2);
  28.     }
  29.      
  30.     int main()
  31.     {
  32.         cin>>n;
  33.         for(int i = 0;i<n;i++){
  34.             cin>>k;
  35.             v.push_back(k);
  36.         }
  37.         sort(v.begin(),v.end());
  38.         ar.push_back(make_pair(v[0],1));
  39.         ll temp = 0;
  40.         for (int i = 1;i<n;i++) {
  41.             if(v[i] != ar[temp].first) {
  42.                 temp++;
  43.                 ar.push_back(make_pair(v[i],1));
  44.             } else {
  45.                 ar[temp].second++;
  46.             }
  47.         }
  48.         memset(dp,-1,sizeof dp);
  49.         if(ar.size()==1){cout<<ar[0].first*ar[0].second;}
  50.         else cout<<solve(0,n);
  51.         return 0;
  52.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement