oj.uz

Submission #374679

# Submission time Handle Problem Language Result Execution time Memory
374679 2021-03-07T20:30:33 Z AlexRex0 Raisins (IOI09_raisins) C++14
100 / 100
 985 ms 28396 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
int res[52][52][52][52];
bool visitado[52][52][52][52];
int matriz[52][52];
int acumulado[52][52];

int suma(int i, int j, int a, int b){
    return acumulado[a][b] - acumulado[i - 1][b] - acumulado[a][j - 1] + acumulado[i - 1][j - 1];
}
int dp(int i, int j, int a, int b){
    if(visitado[i][j][a][b]){
        return res[i][j][a][b];
    }
    if(i == a && j == b){
        return 0;
    }
    visitado[i][j][a][b] = true;
    int aux1 = INT_MAX, aux2 = INT_MAX;
    for(int k = i; k < a; ++k){
        aux1 = min(aux1, dp(i, j, k, b) + dp(k + 1, j, a, b) + suma(i, j, a , b));
    }
    for(int c = j; c < b; ++c){
        aux2 = min(aux2, dp(i, j, a, c) + dp(i, c + 1, a, b) + suma(i, j, a , b));
    }
    res[i][j][a][b] = min(aux1, aux2);
    return res[i][j][a][b];
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> matriz[i][j];
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            acumulado[i][j] = matriz[i][j] + acumulado[i][j - 1];
        }
    }
    for(int j = 1; j <= m; ++j){
        for(int i = 1; i <= n; ++i){
            acumulado[i][j]+= acumulado[i - 1][j];
        }
    }
    cout << dp(1, 1, n, m);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1388 KB Output is correct
8 Correct 13 ms 3840 KB Output is correct
9 Correct 23 ms 5228 KB Output is correct
10 Correct 32 ms 6124 KB Output is correct
11 Correct 29 ms 5356 KB Output is correct
12 Correct 99 ms 10220 KB Output is correct
13 Correct 165 ms 12908 KB Output is correct
14 Correct 44 ms 6636 KB Output is correct
15 Correct 205 ms 14316 KB Output is correct
16 Correct 21 ms 4972 KB Output is correct
17 Correct 87 ms 9836 KB Output is correct
18 Correct 538 ms 21612 KB Output is correct
19 Correct 849 ms 26688 KB Output is correct
20 Correct 985 ms 28396 KB Output is correct