fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. void helper(vector<int>&nums,int n,vector<pair<int,int>>&firstAndLast,vector<bool>&present,vector<vector<int>>&pref){
  6.  
  7.     for(int i=0;i<n;i++){
  8.         int num=nums[i];
  9.         //pref update
  10.         pref[i+1]=pref[i];
  11.         pref[i+1][num]++;
  12.  
  13.         //firstAndLast
  14.         if(firstAndLast[num].first==-1){
  15.             firstAndLast[num]={i,i};
  16.         }else{
  17.             firstAndLast[num].second=i;
  18.         }
  19.  
  20.         //present
  21.         present[num]=true;
  22.     }
  23. }
  24.  
  25. int solve(vector<int>&nums,int st,int end,int k,vector<vector<int>>&pref){
  26.  
  27.    if(k==1){
  28.        return max(nums[st-1],nums[end+1]);
  29.    } 
  30.    if(k==2){
  31.        return nums[st-1]+nums[end+1];
  32.    }
  33.    k-=2;
  34.  
  35.    int ans=nums[st-1]+nums[end+1];
  36.    int cur=50;
  37.  
  38.    while(k>0&&cur>=1){
  39.        int count=pref[end+1][cur]-pref[st][cur];
  40.  
  41.        int taken=min(count,k);
  42.        k-=taken;
  43.        ans+=cur*taken*2;
  44.        cur--;
  45.  
  46.    }
  47.    if(k>0)return INT_MIN;
  48.    return ans;
  49. }
  50. int main() {
  51. 	// your code goes here
  52.  
  53.      int test;
  54.      cin>>test;
  55.  
  56.  
  57.      while(test--){
  58.          int n,k;
  59.          cin>>n>>k;
  60.  
  61.          vector<int>nums(n);
  62.          for(int i=0;i<n;i++){
  63.              cin>>nums[i];
  64.          }
  65.  
  66.          //find the first and last occurance
  67.          vector<pair<int,int>>firstAndLast(51,{-1,-1});
  68.          vector<bool>present(51,false);//if elemnt is preent or not
  69.          vector<vector<int>>pref(n+1,vector<int>(51,0));//pref count only 50 elemnts
  70.          helper(nums,n,firstAndLast,present,pref);
  71.  
  72.          int ans=0;
  73.  
  74.          for(int i=1;i<=50;i++){
  75.              if(present[i]){
  76.                  for(int j=1;j<=50;j++){
  77.                      if(present[j]){
  78.                          int st=firstAndLast[i].first;
  79.                          int end=firstAndLast[j].second;
  80.                          if(st<end){
  81.                              ans=max(ans,solve(nums,st+1,end-1,k,pref));
  82.                          }
  83.                      }
  84.                  }
  85.              }
  86.          }
  87.          cout<<ans<<endl;
  88.  
  89.      }
  90. }
  91.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
3
5 3
1 15 5 7 2
4 2
4 7 9 12
6 6
1 2 3 4 5 6
stdout 
38
21
35
https://ideone.com/KZeQjA
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
secret

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!