Submission #867593

#	Time	Username	Problem	Language	Result	Execution time	Memory
867593		Bula	Raisins (IOI09_raisins)	C++14	25 / 100	5095 ms	35312 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
int n, m, x[55][55], dp[55][55][55][55], pref[55][55];

int rec(int a, int b, int A, int B){
    if(a == A && b == B){
        return 0;
    }
    int sum = pref[A][B] + pref[a - 1][b - 1] - pref[a - 1][B] - pref[A][b - 1];
    for(int i = a; i < A; i++){
        dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, i, B) + rec(i + 1, b, A, B));
    }
    for(int i = b; i < B; i++){
        dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, A, i) + rec(a, i + 1, A, B));
    }
    return dp[a][b][A][B];
}


main(){
    cin >> n >> m;
    for(int i = 1; i <= 50; i++){
        for(int j = 1; j <= 50; j++){
            for(int k = 1; k <= 50; k++){
                for(int l = 1; l <= 50; l++){
                    dp[i][j][k][l] = INT_MAX;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> x[i][j];
            dp[i][j][i][j] = 0; 
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            pref[i][j] = x[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    cout << rec(1, 1, n, m) << endl;
}

Compilation message (stderr)

raisins.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main(){
      | ^~~~

• Subtask 1: 25 / 100