oj.uz

답안 #10097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
10097 2014-10-14T13:30:20 Z sutekine On grid (kriii2_O) C++
1 / 4
 1000 ms 2216 KB 
#include <cstdio>
#include <algorithm>
#define oo 987654321

int R, C, A[311][311], S[311][311], DT[310][310];

int f(int a, int b)
{
    int ans = -oo;
    if( a == R+1 && b == C+1 ) return 0;
    if( a == R+1 || b == C+1 ) return -oo;
    if( DT[a][b] == 0 )
    {
        for(int i = a ; i <= R ; i++ ) for( int j = b ; j <= C ; j++ )
            ans = std::max( ans, S[i][j] - S[a-1][j] - S[i][b-1] + S[a-1][b-1] + f(i+1, j+1) );
        DT[a][b] = ans;
    }
    return DT[a][b];
}

int main()
{
    scanf("%d%d",&R,&C);
    for(int i = 1 ; i <= R ; i++ ) for(int j = 1 ; j <= C ; j++ )
        scanf("%d", &A[i][j]);
    for(int i = 1 ; i <= R ; i++ ) for(int j = 1 ; j <= C ; j++ )
        if( i == 1 && j == 1 ) S[i][j] = A[i][j];
        else S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
    printf("%d", f(1,1));
    return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2216 KB Output is correct
2 Correct 0 ms 2216 KB Output is correct
3 Correct 0 ms 2216 KB Output is correct
4 Correct 0 ms 2216 KB Output is correct
5 Correct 0 ms 2216 KB Output is correct
6 Correct 0 ms 2216 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2216 KB Output is correct
9 Correct 0 ms 2216 KB Output is correct
10 Correct 0 ms 2216 KB Output is correct
11 Correct 0 ms 2216 KB Output is correct
12 Correct 0 ms 2216 KB Output is correct
13 Correct 0 ms 2216 KB Output is correct
14 Correct 0 ms 2216 KB Output is correct
15 Correct 0 ms 2216 KB Output is correct
16 Correct 0 ms 2216 KB Output is correct
17 Correct 0 ms 2216 KB Output is correct
18 Correct 0 ms 2216 KB Output is correct
19 Correct 0 ms 2216 KB Output is correct
20 Correct 0 ms 2216 KB Output is correct
21 Correct 0 ms 2216 KB Output is correct
22 Correct 0 ms 2216 KB Output is correct
23 Correct 0 ms 2216 KB Output is correct
24 Correct 0 ms 2216 KB Output is correct
25 Correct 0 ms 2216 KB Output is correct
26 Correct 0 ms 2216 KB Output is correct
27 Correct 0 ms 2216 KB Output is correct
28 Correct 0 ms 2216 KB Output is correct
29 Correct 0 ms 2216 KB Output is correct
30 Correct 0 ms 2216 KB Output is correct

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 2216 KB Program timed out
2 Halted 0 ms 0 KB -