Submission #798036

#	Time	Username	Problem	Language	Result	Execution time	Memory
798036		aymanrs	Raisins (IOI09_raisins)	C++14	100 / 100	120 ms	24788 KiB

raisins

#include<bits/stdc++.h>
const int MOD = 1e9+7;
using namespace std;
void solve(){
	int n, m;
	cin >> n >> m;
	int dp[n][m][n][m];
	int pr[n][m];
	for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) {
		cin >> pr[i][j];
		dp[0][0][i][j] = 0;
		if(i) pr[i][j] += pr[i-1][j];
		if(j) {
			pr[i][j] += pr[i][j-1];
			if(i) pr[i][j] -= pr[i-1][j-1];
		}
	}
	for(int h = 0;h < n;h++){
		for(int w = h ? 0 : 1;w < m;w++){
			for(int i = 0;i+h < n;i++){
				for(int j = 0;j+w < m;j++){
					dp[h][w][i][j] = pr[i+h][j+w]-(i ? pr[i-1][j+w] : 0)-(j ? pr[i+h][j-1] : 0)+(i&&j ? pr[i-1][j-1] : 0);
					int x = INT_MAX;
					for(int k = 0;k < h;k++) x = min(x, dp[k][w][i][j]+dp[h-k-1][w][i+k+1][j]);
					for(int k = 0;k < w;k++) x = min(x, dp[h][k][i][j]+dp[h][w-k-1][i][j+k+1]);
					dp[h][w][i][j] += x;
				}
			}
		}
	}
	cout << dp[n-1][m-1][0][0] << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

• Subtask 1: 100 / 100