Submission #771866

#	Time	Username	Problem	Language	Result	Execution time	Memory
771866		BlockOG	Raisins (IOI09_raisins)	C++14	100 / 100	132 ms	29352 KiB

raisins

#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

/*
2 3
2 7 5
1 9 5

*/



int main() {
    int n, m; cin >> n >> m;

    vector<vector<int>> nums(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> nums[i][j];

    vector<vector<int>> ps(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ps[i + 1][j + 1] = nums[i][j] + ps[i + 1][j] + ps[i][j + 1] - ps[i][j];

    vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(m))));
    for (int a = n - 1; a >= 0; a--) {
        for (int b = m - 1; b >= 0; b--) {
            for (int c = a; c < n; c++) {
                for (int d = b; d < m; d++) {
                    if (a == c && b == d) continue;

                    dp[a][b][c][d] = ps[n][m] + 1e9;
                    int raisins = ps[c + 1][d + 1] - ps[c + 1][b] - ps[a][d + 1] + ps[a][b];
                    for (int i = a; i < c; i++)
                        dp[a][b][c][d] = min(dp[a][b][c][d], raisins + dp[a][b][i][d] + dp[i + 1][b][c][d]);
                    for (int j = b; j < d; j++)
                        dp[a][b][c][d] = min(dp[a][b][c][d], raisins + dp[a][b][c][j] + dp[a][j + 1][c][d]);
                }
            }
        }
    }

    cout << dp[0][0][n - 1][m - 1] << endl;
}

• Subtask 1: 100 / 100