Submission #1227403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227403		lance0	Raisins (IOI09_raisins)	C++20	100 / 100	167 ms	24884 KiB

raisins

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

int main() {
	int n,m; cin >> n >> m;
	int arr[n][m] = {};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	int pref[n][m] = {};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			pref[i][j] = arr[i][j];
			if (j > 0) {
				pref[i][j] += pref[i][j-1];
			}
			if (i > 0) {
				pref[i][j] += pref[i-1][j];
			}
			if (i > 0 and j > 0) {
				pref[i][j] -= pref[i-1][j-1];
			}
		}
	}
	int dp[n][m][n][m] = {};
	//dimensions
	for (int k = 0; k < n; k++) {
		for (int l = 0; l < m; l++) {
			// top left corner
			for (int i = 0; i+k < n; i++) {
				for (int j = 0; j+l < m; j++) {
					if (k == 0 and l == 0) {
						dp[i][j][i+k][j+l] = 0;
					} else {
						dp[i][j][i+k][j+l] = 2e9;
						//main dp process
						for (int x = 0; x < k; x++) {
							//consider cutting a strip of x*l
							//so e.g. a 3x4 would consider 1x4,2x4 and 2x4,1x4 cuts
							dp[i][j][i+k][j+l] = min(dp[i][j][i+k][j+l], dp[i][j][i+x][j+l]+dp[i+x+1][j][i+k][j+l]);
						}
						for (int x = 0; x < l; x++) {
							//consider cutting a strip of k*x
							dp[i][j][i+k][j+l] = min(dp[i][j][i+k][j+l], dp[i][j][i+k][j+x]+dp[i][j+x+1][i+k][j+l]);
						}
						//no matter what, this costs a specified amount to do any cut on
						dp[i][j][i+k][j+l] += pref[i+k][j+l];
						if (i > 0) {
							dp[i][j][i+k][j+l] -= pref[i-1][j+l];
						}
						if (j > 0) {
							dp[i][j][i+k][j+l] -= pref[i+k][j-1];
						}
						if (i > 0 and j > 0) {
							dp[i][j][i+k][j+l] += pref[i-1][j-1];
						}
					}
				}
			}
		}
	}
	cout << dp[0][0][n-1][m-1];
	return 0;
}

• Subtask 1: 100 / 100