Submission #335587

#	Time	Username	Problem	Language	Result	Execution time	Memory
335587		Joshc	Raisins (IOI09_raisins)	C++11	100 / 100	1034 ms	26988 KiB

raisins

#include <cstdio>
#include <algorithm>
using namespace std;

int prefix[51][51], dp[51][51][51][51];

int ans(int x1, int y1, int x2, int y2) {
	if (x1==x2 && y1==y2) {
		return 0;
	}
	if (dp[x1][y1][x2][y2]!=-1) {
		return dp[x1][y1][x2][y2];
	}
	int best = 2000000000;
	if (x1!=x2) {
		for (int row=x1; row<x2; row++) {
			best = min(best, ans(x1, y1, row, y2)+ans(row+1, y1, x2, y2));
		}
	}
	if (y1 != y2) {
		for (int column=y1; column<y2; column++) {
			best = min(best, ans(x1, y1, x2, column)+ans(x1, column+1, x2, y2));
		}
	}
	dp[x1][y1][x2][y2] = best + prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
	return dp[x1][y1][x2][y2];
}

int main() {
	int n, m, input;
	scanf(" %d %d ", &n, &m);
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			scanf(" %d ", &input);
			prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + input;
		}
	}
	for (int i=0; i<51; i++) {
		for (int j=0; j<51; j++) {
			for (int k=0; k<51; k++) {
				for (int l=0; l<51; l++) {
					dp[i][j][k][l] = -1;
				}
			}
		}
	}
	printf("%d\n", ans(1, 1, n, m));
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf(" %d %d ", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
raisins.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |    scanf(" %d ", &input);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100