oj.uz

답안 #374689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374689 2021-03-07T20:42:23 Z Christopher_Rdz 건포도 (IOI09_raisins) C++17
100 / 100
 1186 ms 26112 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAX 51

int memo[MAX][MAX][MAX][MAX];
int t[MAX][MAX];

int suma(int i, int j, int a, int b){
    return t[a][b] - t[a][j - 1] - t[i - 1][b] + t[i - 1][j - 1];
}

int dp(int i, int j, int a, int b){
    if (i == a and j == b){
        return 0;
    }else{
        if (memo[i][j][a][b] == 1000000000){
          	for (int k = i; k < a; k++){
                memo[i][j][a][b] = min(memo[i][j][a][b], dp(i, j, k, b) + dp(k + 1, j, a, b) + suma(i, j, a, b));
            }
            for (int c = j; c < b; c++){
                memo[i][j][a][b] = min(memo[i][j][a][b], dp(i, j, a, c) + dp(i, c + 1, a, b) + suma(i, j, a, b));
            }
        }
      return memo[i][j][a][b];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> t[i][j];
            t[i][j] += t[i][j - 1] + t[i - 1][j] - t[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= 50; i++){
        for (int j = 1; j <= 50; j++){
            for (int a = 1; a <= 50; a++){
                for (int b = 1; b <= 50; b++){
                    memo[i][j][a][b] = 1000000000;
                }
            }
        }
    }
    cout << dp(1, 1, n, m);
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 26092 KB Output is correct
2 Correct 17 ms 25964 KB Output is correct
3 Correct 17 ms 25964 KB Output is correct
4 Correct 17 ms 25964 KB Output is correct
5 Correct 18 ms 25964 KB Output is correct
6 Correct 17 ms 25964 KB Output is correct
7 Correct 18 ms 25964 KB Output is correct
8 Correct 31 ms 25964 KB Output is correct
9 Correct 50 ms 26112 KB Output is correct
10 Correct 51 ms 25964 KB Output is correct
11 Correct 46 ms 25964 KB Output is correct
12 Correct 129 ms 25964 KB Output is correct
13 Correct 210 ms 25964 KB Output is correct
14 Correct 65 ms 25964 KB Output is correct
15 Correct 251 ms 25964 KB Output is correct
16 Correct 35 ms 25964 KB Output is correct
17 Correct 107 ms 25964 KB Output is correct
18 Correct 640 ms 26092 KB Output is correct
19 Correct 1022 ms 26092 KB Output is correct
20 Correct 1186 ms 26092 KB Output is correct