Submission #374686

#	Time	Username	Problem	Language	Result	Execution time	Memory
374686		Christopher_Rdz	Raisins (IOI09_raisins)	C++17	100 / 100	1212 ms	21228 KiB

raisins

#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] != 0){
            return memo[i][j][a][b];
        }else{
            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 / 100