Submission #335587

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335587	2020-12-13T08:46:31 Z	Joshc	Raisins (IOI09_raisins)	C++11	100 / 100	1034 ms	26988 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	26732 KB	Output is correct
2	Correct	23 ms	26732 KB	Output is correct
3	Correct	19 ms	26732 KB	Output is correct
4	Correct	19 ms	26732 KB	Output is correct
5	Correct	22 ms	26732 KB	Output is correct
6	Correct	19 ms	26732 KB	Output is correct
7	Correct	23 ms	26732 KB	Output is correct
8	Correct	30 ms	26860 KB	Output is correct
9	Correct	42 ms	26848 KB	Output is correct
10	Correct	49 ms	26732 KB	Output is correct
11	Correct	44 ms	26732 KB	Output is correct
12	Correct	134 ms	26732 KB	Output is correct
13	Correct	191 ms	26860 KB	Output is correct
14	Correct	60 ms	26732 KB	Output is correct
15	Correct	228 ms	26988 KB	Output is correct
16	Correct	35 ms	26732 KB	Output is correct
17	Correct	135 ms	26732 KB	Output is correct
18	Correct	611 ms	26860 KB	Output is correct
19	Correct	892 ms	26860 KB	Output is correct
20	Correct	1034 ms	26860 KB	Output is correct