Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <memory.h>
- using namespace std;
- #define ABS(a) ((a>0)?a:-(a))
- #define MIN(a,b) ((a<b)?(a):(b))
- #define MAX(a,b) ((a<b)?(b):(a))
- #define FOR(i,a,n) for (int i=(a);i<(n);++i)
- #define FI(i,n) for (int i=0; i<(n); ++i)
- #define pnt pair <int, int>
- #define mp make_pair
- #define PI 3.14159265358979
- #define MEMS(a,b) memset(a,b,sizeof(a))
- #define LL long long
- #define U unsigned
- int n,m;
- int dp[1010][1010][3];
- int a[1010][1010];
- int was[1010][1010][3];
- int way[1010][1010][3];
- int t;
- int r(int x, int y, int from)
- {
- if ((x==n-1) && (y==m-1))
- return a[x][y];
- if (was[x][y][from]==t)
- return dp[x][y][from];
- was[x][y][from]=t;
- int res=-1000000000;
- if (x<n-1)
- res=max(res,a[x][y]+r(x+1,y,0));
- if ((y<m-1) && (from!=2))
- res=max(res,a[x][y]+r(x,y+1,1));
- if ((y>0) && (from!=1))
- res=max(res,a[x][y]+r(x,y-1,2));
- return dp[x][y][from]=res;
- }
- int main()
- {
- #ifdef Fcdkbear
- freopen("in.txt","r",stdin);
- #endif
- t=0;
- while (1)
- {
- t++;
- scanf("%d%d",&n,&m);
- if ((n==0) && (m==0))
- break;
- //MEMS(was,0);
- FOR(i,0,n)
- FOR(j,0,m)
- scanf("%d",&a[i][j]);
- int res=r(0,0,0);
- printf("Teste %d\n",t);
- cout<<res<<endl<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment