Submission #10103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
10103	2014-10-15T06:15:59 Z	gs14030	On grid (kriii2_O)	C++	1 / 4	1000 ms	1836 KB

O

#include <cstdio>
int n,m,gs[310][310],hs[310][310];
int koi(int a,int b)
{
    if(hs[a][b]!=-987654321) return hs[a][b];
    int x=0,y=0;
    if(a==n){ for(int i=b; i<=m; i++) x+=gs[a][i]; return x; }
    if(b==m){ for(int i=a; i<=n; i++) x+=gs[i][b]; return x; }
    for(int i=a; i<=n; i++)
        for(int j=b; j<=m; j++) y+=gs[i][j];
    for(int i=a; i<n; i++)
        for(int j=b; j<m; j++)
        {
            x=0;
            for(int p=a; p<=i; p++)
                for(int q=b; q<=j; q++) x+=gs[p][q];
                x+=koi(i+1,j+1);
            if(y<x) y=x;
        }
    hs[a][b]=y;
    return hs[a][b];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%d",&gs[i][j]);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) hs[i][j]=-987654321;
    printf("%d",koi(1,1));
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1836 KB	Output is correct
2	Correct	0 ms	1836 KB	Output is correct
3	Correct	0 ms	1836 KB	Output is correct
4	Correct	16 ms	1836 KB	Output is correct
5	Correct	0 ms	1836 KB	Output is correct
6	Correct	0 ms	1836 KB	Output is correct
7	Correct	0 ms	1836 KB	Output is correct
8	Correct	0 ms	1836 KB	Output is correct
9	Correct	0 ms	1836 KB	Output is correct
10	Correct	0 ms	1836 KB	Output is correct
11	Correct	0 ms	1836 KB	Output is correct
12	Correct	0 ms	1836 KB	Output is correct
13	Correct	4 ms	1836 KB	Output is correct
14	Correct	0 ms	1836 KB	Output is correct
15	Correct	0 ms	1836 KB	Output is correct
16	Correct	0 ms	1836 KB	Output is correct
17	Correct	0 ms	1836 KB	Output is correct
18	Correct	0 ms	1836 KB	Output is correct
19	Correct	0 ms	1836 KB	Output is correct
20	Correct	0 ms	1836 KB	Output is correct
21	Correct	16 ms	1836 KB	Output is correct
22	Correct	8 ms	1836 KB	Output is correct
23	Correct	0 ms	1836 KB	Output is correct
24	Correct	0 ms	1836 KB	Output is correct
25	Correct	0 ms	1836 KB	Output is correct
26	Correct	20 ms	1836 KB	Output is correct
27	Correct	0 ms	1836 KB	Output is correct
28	Correct	4 ms	1836 KB	Output is correct
29	Correct	4 ms	1836 KB	Output is correct
30	Correct	12 ms	1836 KB	Output is correct

Subtask #2

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	1832 KB	Program timed out
2	Halted	0 ms	0 KB	-