Menu

SPOJ SHUB1307 – Gupta ji Birthday !!

January 1, 2017 - SPOJ

Language: C++

#include<bits/stdc++.h>
    using namespace std;
    #define rep(i,n) for(i=0;i<n;i++)
    #define ll long long
    #define elif else if
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    bool dp[105][105][505];
    int grid[105][105];
    int main()
    {
      // freopen("in.txt","r",stdin);
      // freopen("out","w",stdout);
      ios_base::sync_with_stdio(0);
      int t;
      cin>>t;
      assert(1<=t && t<=10);
      while(t--)
      {
         int n,m,i,j,k,p;
        cin>>n>>m>>p;
        rep(i,n)
        {
          rep(j,m)
          {
            cin>>grid[i][j];
            rep(k,501)
              dp[i][j][k]=false;
          }
        }
        // if(grid[0][0]>k)
        //   cout<<"y";
       for(i=0;i<n;i++)
       {
        for(j=0;j<m;j++)
        {
          for(k=grid[i][j];k<=p;k++)
          {
            if( i==0 && j==0)
            {
              if(k==grid[i][j])
                dp[i][j][k] = true;
            }
            elif(i==0)
            {
              dp[i][j][k] = (dp[i][j][k] || dp[i][j-1][k-grid[i][j]]); 
            }
            elif(j==0)
            {
              dp[i][j][k] = (dp[i][j][k] || dp[i-1][j][k-grid[i][j]]); 
            }
            else
            {
              dp[i][j][k] = (dp[i][j][k] || dp[i][j-1][k-grid[i][j]]); 
              dp[i][j][k] = (dp[i][j][k] || dp[i-1][j][k-grid[i][j]]); 
              dp[i][j][k] = (dp[i][j][k] || dp[i-1][j-1][k-grid[i][j]]); 
            }
          }
        }
      }
      int ans=0;
      for(ans=k;ans>=0;ans--)
        if(dp[n-1][m-1][ans])
          break;
       cout<<ans<<endl;
      }
     return 0;
    }

(113)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on VK

Author of this post : Anuj Chauhan

Leave a Reply

Your email address will not be published. Required fields are marked *