-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathAMR11E_re.cpp
More file actions
63 lines (57 loc) · 2.02 KB
/
AMR11E_re.cpp
File metadata and controls
63 lines (57 loc) · 2.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<iostream>
using namespace std;
int a[501][501];
int b[501][501];
int main(){
int t;
scanf("%d",&t);
while(t--){
int m,n;
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
if(m==1){
int sum=0,min=1000;
for(int i=0;i<n;i++){
sum+=a[0][i];
if(sum<min)min=sum;
}
if(min>0)printf("1\n");
else printf("%d\n",1-min);
continue;
}
m--;n--;
b[m][n]=0;
for(int i=m-1;i>=0;i--){
b[i][n]=b[i+1][n]+a[i][n];
}
for(int i=n-1;i>=0;i--){
b[m][i]=b[m][i+1]+a[m][i];
}
for(int i=m-1,j=n-1;i>=0||j>=0;i--,j--){
b[i][j]=a[i][j]+max(b[i+1][j],b[i][j+1]);
for(int k=i-1;k>=0;k--){
b[k][j]=a[k][j]+max(b[k+1][j],b[k][j+1]);
}
for(int l=j-1;l>=0;l--){
b[i][l]=a[i][l]+max(b[i+1][l],b[i][l+1]);
}
}
/*m++;n++;
printf("\n");
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
printf("%d\t",b[i][j]);
}
printf("\n");
}*/
if(b[0][0]>0)printf("1\n");
else
printf("%d\n",1-b[0][0]);
}
return 0;
}