11 months ago

suryansh jaiswal • 370

Lucknow

Question 1 solution

void solve()
{
int n;
cin>>n;
int x,y,z;
cin>>x>>y>>z;
vector<int> v(n);
f(i,n)
cin>>v[i];

vector<pair<int,pair<int,int>>> three;  
vector<pair<int,pair<int,int>>> two;
vector<pair<int,pair<int,int>>> one; 

int sum=0;
f(i,3)
{
sum+=v[i];
} 
three.pb({sum,{0,2}});
for(int i=3;i<n;i++)
{
    sum-=v[i-3];
    sum+=v[i];
    three.pb({sum,{i-2,i}});
}
sum=0;
f(i,2)
{
sum+=v[i];
} 
two.pb({sum,{0,1}});
for(int i=2;i<n;i++)
{
    sum-=v[i-2];
    sum+=v[i];
    two.pb({sum,{i-1,i}});
}

for(int i=0;i<n;i++)
{
    one.pb({v[i],{i,i}});
}
vector<int> vis(n,0);
int ans=0;
sort(three.begin(),three.end());
sort(two.begin(),two.end());
sort(one.begin(),one.end());
while(z && !three.empty())
{
    pair<int,pair<int,int>> p=three.back();
    int a=p.first;
    int i=p.second.first;
    int j=p.second.second;
    bool flag=false;
    for(int k=i;k<=j;k++)
    {
      if(vis[k])
        flag=true;
    }
    three.pop_back();
    if(flag)
        continue;
    else
    {
        z--;
     for(int k=i;k<=j;k++)
    {
      vis[k]=1;
    }   
    ans+=a;
    }
}

while(y && !two.empty())
{
    pair<int,pair<int,int>> p=two.back();
    //cout<<p<<endl;
    int a=p.first;
    int i=p.second.first;
    int j=p.second.second;
    bool flag=false;
    for(int k=i;k<=j;k++)
    {
      if(vis[k])
        flag=true;
    }
    two.pop_back();
    if(flag)
        continue;
    else
    {
        y--;
        //cout<<a<<endl;
     for(int k=i;k<=j;k++)
    {
      vis[k]=1;
    }   
    ans+=a;
    }
}
//cout<<vis<<endl;
while(x && !one.empty())
{
    pair<int,pair<int,int>> p=one.back();
    int a=p.first;
    int i=p.second.first;
    int j=p.second.second;
    bool flag=false;
    for(int k=i;k<=j;k++)
    {
      if(vis[k])
        flag=true;
    }
    one.pop_back();
    if(flag)
        continue;
    else
    {
        x--;
     for(int k=i;k<=j;k++)
    {
      vis[k]=1;
    }   
    ans+=a;
    }
}
cout<<ans<<endl;





}


int32_t main()
{
    fast
   /* int t;
    cin>>t;
    while(t--)*/
    solve();        
}