Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- typedef long long ll;
- using namespace std;
- ll n,k;
- vector <ll> v;
- vector <pair <ll,ll> > ar;
- ll dp[100005];
- ll solve(ll i,ll elements){
- ll temp1,temp2,temp3,c1 = 0,c2 = 0, found = 0;
- if(elements== 0) return 0;
- if(i>=ar.size()) return -1e17;
- if(dp[i] +1) return dp[i];
- if(i!=0 ) {temp1 = ar[i-1].second; if(ar[i].first-ar[i-1].first==1){elements-=temp1;ar[i-1].second= 0;}}
- 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;}}
- temp3 = ar[i].second;
- ar[i].second = 0;
- if(found){
- c1 = solve(i+2,elements-temp3)+ar[i].first*temp3;
- } else {
- c1 = solve(i+1,elements-temp3)+ar[i].first*temp3;
- }
- ar[i].second = temp3;
- if(i!=0) { if(ar[i].first-ar[i-1].first==1){elements+=temp1;ar[i-1].second= temp1;}}
- if(i!=ar.size()-1){if(ar[i+1].first-ar[i].first==1){elements+=temp2;ar[i+1].second = temp2;}}
- c2 = solve(i+1,elements);
- return dp[i] = max(c1,c2);
- }
- int main()
- {
- cin>>n;
- for(int i = 0;i<n;i++){
- cin>>k;
- v.push_back(k);
- }
- sort(v.begin(),v.end());
- ar.push_back(make_pair(v[0],1));
- ll temp = 0;
- for (int i = 1;i<n;i++) {
- if(v[i] != ar[temp].first) {
- temp++;
- ar.push_back(make_pair(v[i],1));
- } else {
- ar[temp].second++;
- }
- }
- memset(dp,-1,sizeof dp);
- if(ar.size()==1){cout<<ar[0].first*ar[0].second;}
- else cout<<solve(0,n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement