제출 #767251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767251		Gabi88	Raisins (IOI09_raisins)	C++14	100 / 100	944 ms	88932 KiB

raisins

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

#define LL long long

LL n, m, dp[58][58][58][58], sub[58][58];

LL dodaj(int px, int py, int cx, int cy){
	int d1 = 0, d2 = 0, d3 = 0;
	if (px >= 0 and py >= 0) d1 = sub[px][py];
	if (px >= 0) d2 = sub[px][cy];
	if (py >= 0) d3 = sub[cx][py];
	return d1 + sub[cx][cy] - d2 - d3;
}

LL reks(int px, int py, int cx, int cy){
	LL suma = dodaj(px-1, py-1, cx-1, cy-1), res = 1000000009;
	if (px+1 == cx and py+1 == cy) return dp[px][py][cx][cy];
	else if (dp[px][py][cx][cy] >= suma) return dp[px][py][cx][cy];
//	cout << suma << " -> " << px << " " << py << " " << cx << " " << cy << endl;
	for(int i=px+1; i < cx; i++) res = min(res, reks(px, py, i, cy) + reks(i, py, cx, cy) + suma);
	for(int i=py+1; i < cy; i++) res = min(res, reks(px, py, cx, i) + reks(px, i, cx, cy) + suma);
//	cout << px << " " << py << " | " << cx << " " << cy << " | " << res << endl;
	return dp[px][py][cx][cy] = res;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m;
	for(int i1=0; i1 < 58; i1++) for(int i2=0; i2 < 58; i2++) for(int i3=0; i3 < 58; i3++) for(int i4=0; i4 < 58; i4++) dp[i1][i2][i3][i4] = -1;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> dp[i][j][i+1][j+1];
			if (i == 0 and j == 0) sub[0][0] = dp[0][0][1][1];
			else if (i == 0) sub[0][j] = sub[0][j-1] + dp[0][j][1][j+1];
			else if (j == 0) sub[i][0] = sub[i-1][0] + dp[i][0][i+1][1];
			else sub[i][j] = sub[i][j-1] + sub[i-1][j] - sub[i-1][j-1] + dp[i][j][i+1][j+1];
		}
	}
	cout << reks(0, 0, n, m)-sub[n-1][m-1]; return 0;
}

• Subtask 1: 100 / 100