codefoce 416 B

/*codeforce 416 B*/
# include<iostream>
# include<cstdio>
# include<cstring>
# include<cmath>
# include<cstdlib>
# include<algorithm>
using namespace std;
const int N=100008;
int s[N][8];
int dp[N][8];
int n,m;
int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
               cin>>s[i][j];
               memset(dp,0,sizeof(dp));
        int x=0;
        for(int i=1;i<=m;i++)
        {
            x=x+s[1][i];
            dp[1][i]=x;
        }
        x=0;
        for(int i=1;i<=n;i++)
        {
            x=x+s[i][1];
            dp[i][1]=x;
        }
        for(int i=2;i<=n;i++)
        {
            for(int j=2;j<=m;j++)
            {
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])+s[i][j];
            }
        }
        for(int i=1;i<n;i++)
            cout<<dp[i][m]<<" ";
        cout<<dp[n][m]<<endl;
    }
    return 0;
}
/*    :
      :
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+s[i][j];
dp[i][j]   i   j          
   i         i+1         ,
      j     i-1      j-1    i     ,
                ,           j    i     
*/

좋은 웹페이지 즐겨찾기