467C. George and Job - Codeforces Solution C++

➤  Problem Link : 467C. George and Job 

✅ C++ Solution :

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

#define ll long long int

int main()
{
	int n,m,k;
	cin>>n>>m>>k;

	ll dp[n+1][k+1];
	for(int i=0;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
			dp[i][j]=-1;
	}
	
	for(int i=0;i<=n;i++)
	    dp[i][0]=0;

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

	ll cum[n+1];
	cum[1]=arr[1];
	for(int i=2;i<=n;i++)
		cum[i]=arr[i]+cum[i-1];
	cum[0]=0;
	for(int i=1;i<=n;i++)
	{
	    if(i>=m)
			dp[i][1]=max(dp[i-1][1],cum[i]-cum[i-m]);
	}

	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=k;j++)
		{
			if(i>=m && dp[i-m][j-1]!=-1)
				dp[i][j]=max(dp[i-1][j],cum[i]-cum[i-m]+dp[i-m][j-1]);
		}

	}
/*	
	for(int i=0;i<=n;i++)
	{
	    for(int j=0;j<=k;j++)
	        cout<<dp[i][j]<<" ";
	    cout<<endl;     
	}*/

	cout<<dp[n][k];
}

 

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.