Submission #374674

#	Time	Username	Problem	Language	Result	Execution time	Memory
374674		AlexRex0	Raisins (IOI09_raisins)	C++14	100 / 100	990 ms	28396 KiB

raisins

#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 / 100