Submission #646034

#	Time	Username	Problem	Language	Result	Execution time	Memory
646034		Genius3435	Raisins (IOI09_raisins)	C++17	100 / 100	247 ms	21412 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

template <typename T, typename U>
bool ckmin(T &t, const U& u) {
    return u<t ? t=u,true : false;
}

int constexpr N = 52;
int r[N][N];
int ps[N][N];
int dp[N][N][N][N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> r[i][j];
            ps[i+1][j+1] = r[i][j] + ps[i+1][j] + ps[i][j+1] - ps[i][j];
        }
    }

    for (int di = 0; di < n; ++di) {
        for (int dj = 0; dj < m; ++dj) {
            for (int li = 0; li < n-di; ++li) {
                for (int lj = 0; lj < m-dj; ++lj) {
                    int ri = li + di, rj = lj + dj;
                    dp[li][lj][ri][rj] = (di+dj == 0 ? -r[li][lj] : 2e9);
                    for (int mi = li; mi < ri; ++mi) ckmin(dp[li][lj][ri][rj], dp[li][lj][mi][rj] + dp[mi+1][lj][ri][rj]);
                    for (int mj = lj; mj < rj; ++mj) ckmin(dp[li][lj][ri][rj], dp[li][lj][ri][mj] + dp[li][mj+1][ri][rj]);
                    dp[li][lj][ri][rj] += ps[ri+1][rj+1] - ps[ri+1][lj] - ps[li][rj+1] + ps[li][lj];
                }
            }
        }
    }
    cout << dp[0][0][n-1][m-1] << '\n';
}

• Subtask 1: 100 / 100