448C. Painting Fence - Codeforces Solution C++

➤  Problem Link : 448C. Painting Fence 

✅ C++ Solution :

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

#define ll long long int

ll divMerge(int a,int b,ll arr[],int n)
{
	if(a==b)
		return 1;
	ll ans=0;
	ll minH=pow(10,9)+1;
	for(int i=a;i<=b;i++)
	{
		if(arr[i]<minH)
			minH=arr[i];
	}
	ll minCnt=0;
	for(int i=a;i<=b;i++)
	{
		if(arr[i]==minH)
			minCnt++;
		arr[i]-=minH;
	}
	ans=minH;
	/*if(minCnt<minH)
	{
	    for(int i=a;i<=b;i++)
	    if(arr[i]==minH)
	        arr[i]=0;
	}
	else
	{
	    for(int i=a;i<=b;i++)
	        arr[i]-=minH;
	}*/
	int m=a,l=a;
	while(m<=b)
	{
		while(m<=b && arr[m]==0)
			m++;
		if(m>b)
			break;
		l=m;
		while(l<=b && arr[l]!=0)
			l++;
		ans+=divMerge(m,l-1,arr,n);
		m=l;
	}

	return min(ans,(ll)b-a+1);


}

int main()
{
	int n;
	cin>>n;
	ll arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];

	cout<<divMerge(0,n-1,arr,n);
}

 

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.