Submission #531386

#	Time	Username	Problem	Language	Result	Execution time	Memory
531386		Alan	Raisins (IOI09_raisins)	C++17	100 / 100	670 ms	30012 KiB

raisins

#include <bits/stdc++.h>
#define I using
#define WA using namespace std;
#define on using ll = long long;
#define Test(x) int AlanIQ = -(x);
#define should ld =
#define quit long double;
#define OI int
#define forever main
#define Alan cin.tie(0);
#define fai(x) ios::ios_base::sync_with_stdio(!x);
#define Sharky return
#define orz 0;

WA on Test (109)

ll dp[51][51][51][51], a[51][51], ps[51][51];
bool calc[51][51][51][51];
ll n, m;

ll solve (ll i, ll j, ll k, ll l) {
	if (i == j || k == l) return 0;
	if (calc[i][j][k][l]) return dp[i][j][k][l];
	calc[i][j][k][l] = true;
	dp[i][j][k][l] = 1e18;
	for (int mid = i+1; mid <= j; mid++) dp[i][j][k][l] = min(dp[i][j][k][l], solve(i,mid,k,l) + solve(mid,j,k,l));
	for (int mid = k+1; mid <= l; mid++) dp[i][j][k][l] = min(dp[i][j][k][l], solve(i,j,k,mid) + solve(i,j,mid,l));
	return dp[i][j][k][l] = dp[i][j][k][l] + ps[j][l]-ps[i][l]-ps[j][k]+ps[i][k];
}

I should quit OI forever () {
	Alan fai (true)
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			dp[i-1][i][j-1][j] = 0;
			calc[i-1][i][j-1][j] = true;
			ps[i][j] = a[i][j] + ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1];
		}
	}
	cout << solve(0, n, 0, m) << "\n";

	Sharky orz
}

• Subtask 1: 100 / 100