331A2. Oh Sweet Beaverette - Codeforces Solution C++

➤  Problem Link : 331A2. Oh Sweet Beaverette 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int main()
{
	int n;
	cin>>n;
	unordered_map<ll,int> right;
	ll arr[n+1];
	ll poscum[n+1];
	poscum[0]=0;

	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
		right[arr[i]]=i;
		if(arr[i]>0)
			poscum[i]=arr[i]+poscum[i-1];
		else
			poscum[i]=poscum[i-1];
	}

	ll diff=LONG_MIN,li=-1,ri=-1;
	ll currdiff;
	for(int i=1;i<=n;i++)
	{
		int ind = right[arr[i]];
		if(ind <= i)
			continue;

		currdiff=poscum[ind]-poscum[i-1];
		if(arr[i]<0)
			currdiff+=arr[i]*2;

		if(currdiff > diff)
		{
			diff=currdiff;
			li=i;
			ri=ind;
		}

	}
	vector<ll> cut;
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		if(i<li || i>ri)
			cut.push_back(i);
		else if(i>li && i < ri && arr[i]<0)
			cut.push_back(i);
		else
			ans+=arr[i];
	}

	cout<<ans<<" "<<cut.size()<<"\n";
	for(auto it : cut)
		cout<<it<<" ";



}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.