Submission #659360

#	Time	Username	Problem	Language	Result	Execution time	Memory
659360		Trisanu_Das	Raisins (IOI09_raisins)	C++17	100 / 100	253 ms	20968 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
 
int dp[51][51][51][51], a[51][51], pref[51][51];
 
int main() {
    int n, m; cin >> n >> m;
    for(int i = 1; i < n + 1; i++) for(int j = 1; j < m + 1; j++){
        cin >> a[i][j];
        pref[i][j] = pref[i - 1][j] + pref[i][j - 1] + a[i][j] - pref[i - 1][j - 1];
    }
 
    for(int i = 1; i < n + 1; i++) for(int j = 1; j < m + 1; j++) for(int k = 1; k < n - i + 2; k++) for(int l = 1;  l < m - j + 2; l++) {
        if (i == 1 && j == 1) continue;
        int mn = INT_MAX;
        for(int x = 1; x < i; x++) mn = min(mn, dp[k][l][x][j] + dp[k + x][l][i - x][j]);
        for(int x = 1; x < j; x++) mn = min(mn, dp[k][l][i][x] + dp[k][l + x][i][j - x]);
        dp[k][l][i][j] = mn + pref[k + i - 1][l + j - 1] + pref[k - 1][l - 1] - pref[k + i - 1][l - 1] - pref[k - 1][l + j - 1];
    }
    cout << dp[1][1][n][m];
    return 0;
}

• Subtask 1: 100 / 100