oj.uz

Submission #374674

# Submission time Handle Problem Language Result Execution time Memory
374674 2021-03-07T20:23:48 Z AlexRex0 Raisins (IOI09_raisins) C++14
100 / 100
 990 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(){
    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 1 ms 1132 KB Output is correct
7 Correct 2 ms 1388 KB Output is correct
8 Correct 12 ms 3820 KB Output is correct
9 Correct 22 ms 5228 KB Output is correct
10 Correct 33 ms 6124 KB Output is correct
11 Correct 27 ms 5356 KB Output is correct
12 Correct 96 ms 10348 KB Output is correct
13 Correct 176 ms 12908 KB Output is correct
14 Correct 43 ms 6636 KB Output is correct
15 Correct 211 ms 14188 KB Output is correct
16 Correct 18 ms 5100 KB Output is correct
17 Correct 82 ms 9836 KB Output is correct
18 Correct 522 ms 21740 KB Output is correct
19 Correct 845 ms 26476 KB Output is correct
20 Correct 990 ms 28396 KB Output is correct