Submission #444634

#	Time	Username	Problem	Language	Result	Execution time	Memory
444634		gratus907	Raisins (IOI09_raisins)	C++17	100 / 100	540 ms	70148 KiB

raisins

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

int n, m;
int r[52][52];
int pr[52][52];
int s[52][52][52][52];
int dp[52][52][52][52];

int solve(int r1, int c1, int r2, int c2) {
    if (r1 > r2 || c1 > c2) return 0;
    if (r1 == r2 && c1 == c2) return 0;
    if (dp[r1][c1][r2][c2]) return dp[r1][c1][r2][c2];
    int val = INT_MAX;
    int tot = s[r1][c1][r2][c2];
    
    for (int i = r1; i < r2; i++)
        val = min(val, tot + solve(r1, c1, i, c2) + solve(i+1, c1, r2, c2));
    for (int i = c1; i < c2; i++)
        val = min(val, tot + solve(r1, c1, r2, i) + solve(r1, i+1, r2, c2));
    
    return dp[r1][c1][r2][c2] = val;
}
int32_t main() {
 	usecppio
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> r[i][j];
            pr[i][j] = pr[i-1][j] + pr[i][j-1] - pr[i-1][j-1] + r[i][j];
        }
    }
    
    for (int r2 = 1; r2 <= n; r2++)
        for (int c2 = 1; c2 <= m; c2++)
            for (int r1 = 1; r1 <= r2; r1++)
                for (int c1 = 1; c1 <= c2; c1++)
                    s[r1][c1][r2][c2] = pr[r2][c2]-pr[r2][c1-1]-pr[r1-1][c2]+pr[r1-1][c1-1];

    cout << solve(1, 1, n, m) << '\n';
}

• Subtask 1: 100 / 100