Submission #720037

#	Time	Username	Problem	Language	Result	Execution time	Memory
720037		a_aguilo	Raisins (IOI09_raisins)	C++14	100 / 100	1612 ms	29376 KiB

raisins

#include<bits/stdc++.h>

using namespace std;

int N, M;
vector<vector<vector<vector<int>>>> DP;
//DP[x1][x2][y1][y2];
vector<vector<int>> preSum, raisinsMap;

int getSum(int x1, int x2, int y1, int y2){
	int ans;
	if(x1 <= 0){
		if(y1 <= 0) ans = preSum[x2][y2];
		else ans = preSum[x2][y2] - preSum[x2][y1-1];
	}else{
		if(y1 <= 0) ans = preSum[x2][y2]-preSum[x1-1][y2];
		else{
			ans = preSum[x2][y2] + preSum[x1-1][y1-1] - preSum[x2][y1-1] - preSum[x1-1][y2];
		}
	}
	return ans;
}

int solve(int x1, int x2, int y1, int y2){
	if(x1 == x2 && y1 == y2) return 0;
	if(DP[x1][x2][y1][y2] != -1) return DP[x1][x2][y1][y2];
	int payNow = getSum(x1, x2, y1, y2);
	if(x1 == x2){
		int ans = solve(x1, x2, y1+1, y2);
		for(int dist = 1; (y1 + dist + 1) <= y2; ++dist){
			ans = min(ans, solve(x1, x2, y1, y1+dist) + solve(x1, x2, y1+dist+1, y2));
		}
		//cout << "x from " << x1 << " to " << x2 << "\t y from " << y1 << " to " << y2 << "\t value paid " << ans << endl;
		return DP[x1][x2][y1][y2] = payNow + ans;
	}else if(y1 == y2){
		int ans = solve(x1+1, x2, y1, y2);
		for(int dist = 1; (x1 + dist + 1) <= x2; ++dist){
			ans = min(ans, solve(x1, x1+dist, y1, y2) + solve(x1+dist+1, x2, y1, y2));
		}
		//cout << "x from " << x1 << " to " << x2 << "\t y from " << y1 << " to " << y2 << "\t value paid " << ans << endl;
		return DP[x1][x2][y1][y2] = payNow + ans;
	}else{
		int ans = solve(x1, x2, y1, y1) + solve(x1, x2, y1+1, y2);
		for(int dist = 1; (y1 + dist + 1) <= y2; ++dist){
			ans = min(ans, solve(x1, x2, y1, y1+dist) + solve(x1, x2, y1+dist+1, y2));
		}
		for(int dist = 0; (x1 + dist + 1) <= x2; ++dist){
			ans = min(ans, solve(x1, x1+dist, y1, y2) + solve(x1+dist+1, x2, y1, y2));
		}
		//cout << "x from " << x1 << " to " << x2 << "\t y from " << y1 << " to " << y2 << "\t value paid " << ans << endl;
		return DP[x1][x2][y1][y2] = payNow + ans;
	}
}

int main(){
	cin >> N >> M;
	raisinsMap = vector<vector<int>>(N, vector<int>(M));
	preSum = vector<vector<int>>(N, vector<int>(M));
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < M; ++j){
			cin >> raisinsMap[i][j];
			preSum[i][j] = raisinsMap[i][j];
			if(i > 0 and j > 0){
				preSum[i][j] += preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
			}else{
				if(i > 0) preSum[i][j] += preSum[i-1][j];
				if(j > 0) preSum[i][j] += preSum[i][j-1];
			}
			//cout << preSum[i][j] << endl;
		}
	}
	DP = vector<vector<vector<vector<int>>>>(N, vector<vector<vector<int>>>(N, vector<vector<int>>(M, vector<int>(M, -1))));
	cout << solve(0, N-1, 0, M-1) << endl;
	return 0;
}

• Subtask 1: 100 / 100