Submission #337478

#	Time	Username	Problem	Language	Result	Execution time	Memory
337478		arbor	Raisins (IOI09_raisins)	C++17	30 / 100	1010 ms	22880 KiB

raisins

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 55;
int N, M, ps[MN][MN], dp[MN][MN][MN][MN];

int go(int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return 0;
    int ret = 1e9;
    for (int nx = x1 + 1; nx <= x2; nx++)
        ret = min(ret, go(x1, y1, nx - 1, y2) + go(nx, y1, x2, y2));
    for (int ny = y1 + 1; ny <= y2; ny++)
        ret = min(ret, go(x1, y1, x2, ny - 1) + go(x1, ny, x2, y2));
    ret += ps[x2][y2] - ps[x2][y1 - 1] - ps[x1 - 1][y1] + ps[x1 - 1][y1 - 1];
    return dp[x1][y1][x2][y2] = ret;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> ps[i][j], ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
    cout << go(1, 1, N, M) << '\n';
    return 0;
}

• Subtask 1: 30 / 100