Submission #1198877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198877		AMel0n	Raisins (IOI09_raisins)	C++20	100 / 100	417 ms	29512 KiB

raisins

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first 
#define S second

int N, M;
vector<vector<vector<vector<int>>>> dp;
vector<vector<int>> ras;

int solve(int a, int b, int c, int d) {
    if (a == b && c == d) return 0;
    if (dp[a][b][c][d] != INT_MIN) return dp[a][b][c][d];
    int mn = 1e8;
    for(int i = a; i < b; i++) mn = min(mn, solve(a, i, c, d) + solve(i + 1, b, c, d));
    for(int i = c; i < d; i++) mn = min(mn, solve(a, b, c, i) + solve(a, b, i + 1, d));
    return dp[a][b][c][d] = mn + ras[b+1][d+1] - ras[b+1][c] - ras[a][d+1] + ras[a][c];
}

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M;
    ras.resize(N+1, vector<int>(M+1));
    dp.resize(N, vector<vector<vector<int>>>(N, vector<vector<int>>(M, vector<int>(M, INT_MIN))));
    FOR(r, N) {
        FOR(c, M) {
            cin >> ras[r+1][c+1];
            ras[r+1][c+1] += ras[r][c+1] + ras[r+1][c] - ras[r][c];
        }
    }

    cout << solve(0,N-1,0,M-1);
}

• Subtask 1: 100 / 100