oj.uz

Submission #374689

# Submission time Handle Problem Language Result Execution time Memory
374689 2021-03-07T20:42:23 Z Christopher_Rdz Raisins (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

# Verdict Execution time Memory 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