forget_it's blog

By forget_it, history, 4 years ago, In English

Can anyone please tell me why my solution is not working for larger subtask,(while smaller is correct)

I made a dp to (i,j), where i denote number of stack inclused , while j represent number of plates need to choose.

Problem Link

#include<bits/stdc++.h>                   
#define ll long long                      
#define ld long double                    
using namespace std;             

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.flush();
	ll t=1;
	ll CaseN=1; 
	cin>>t;
	while(t--)
	{
		ll ans=0;
		ll n,k,A[100][100],p;
		cin>>n>>k>>p;
		ll c=0;
		memset(A,0,sizeof(A));
		for(ll i=1;i<=n;i++)
		{
			c=0;
			for(ll j=1;j<=k;j++)
			{
				ll z;
				cin>>z;
				c+=z;
				A[i][j]=c;
			}
		}
		ll dp[101][101];
		dp[0][0]=0;
		for(ll i=1;i<=n;i++)
		{
			dp[i][0]=0;
			}
		for(ll i=1;i<=p;i++)
		{
			dp[0][i]=0;
		}
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=p;j++)
			{
				ll cc=0;
				for(ll l=0;l<=(k,j);l++)
				{
				if(j-l>=0)
			   {cc=max(cc,dp[i-1][j-l]+A[i][l]);}
				}
				dp[i][j]=cc;
			}
		}
		
		
		ans=dp[n][p];
		cout<<"Case #"<<CaseN<<": ";
		CaseN++;
		// print your ans below;
		cout<<ans<<endl;
	}

return 0;
}

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not sure about problem but what do you intend to do while writting l<=(k,j) because 2<=(1,2) returns 1 and 2<=(2,1) returns 0

»
4 years ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

You should get a runtime error on this, P <= N*K = 1500. You are just taking it to be 100. Adjust the dimensions of the dp array.