oj.uz

Submission #10105

# Submission time Handle Problem Language Result Execution time Memory
10105 2014-10-15T06:44:57 Z gs14030 On grid (kriii2_O) C++
1 / 4
 1000 ms 2212 KB 
#include <cstdio>
int n,m,gs[310][310],hs[310][310],gshs[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=gshs[i][j]+gshs[a-1][b-1]-gshs[a-1][j]-gshs[i][b-1];
            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;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) gshs[i][j]+=gs[i][j]+gshs[i-1][j]+gshs[i][j-1]-gshs[i-1][j-1];
    printf("%d",koi(1,1));
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0.0 / 3.0

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