Submission #767251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
767251	2023-06-26T14:34:24 Z	Gabi88	Raisins (IOI09_raisins)	C++14	100 / 100	944 ms	88932 KB

raisins

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

#define LL long long

LL n, m, dp[58][58][58][58], sub[58][58];

LL dodaj(int px, int py, int cx, int cy){
	int d1 = 0, d2 = 0, d3 = 0;
	if (px >= 0 and py >= 0) d1 = sub[px][py];
	if (px >= 0) d2 = sub[px][cy];
	if (py >= 0) d3 = sub[cx][py];
	return d1 + sub[cx][cy] - d2 - d3;
}

LL reks(int px, int py, int cx, int cy){
	LL suma = dodaj(px-1, py-1, cx-1, cy-1), res = 1000000009;
	if (px+1 == cx and py+1 == cy) return dp[px][py][cx][cy];
	else if (dp[px][py][cx][cy] >= suma) return dp[px][py][cx][cy];
//	cout << suma << " -> " << px << " " << py << " " << cx << " " << cy << endl;
	for(int i=px+1; i < cx; i++) res = min(res, reks(px, py, i, cy) + reks(i, py, cx, cy) + suma);
	for(int i=py+1; i < cy; i++) res = min(res, reks(px, py, cx, i) + reks(px, i, cx, cy) + suma);
//	cout << px << " " << py << " | " << cx << " " << cy << " | " << res << endl;
	return dp[px][py][cx][cy] = res;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m;
	for(int i1=0; i1 < 58; i1++) for(int i2=0; i2 < 58; i2++) for(int i3=0; i3 < 58; i3++) for(int i4=0; i4 < 58; i4++) dp[i1][i2][i3][i4] = -1;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> dp[i][j][i+1][j+1];
			if (i == 0 and j == 0) sub[0][0] = dp[0][0][1][1];
			else if (i == 0) sub[0][j] = sub[0][j-1] + dp[0][j][1][j+1];
			else if (j == 0) sub[i][0] = sub[i-1][0] + dp[i][0][i+1][1];
			else sub[i][j] = sub[i][j-1] + sub[i-1][j] - sub[i-1][j-1] + dp[i][j][i+1][j+1];
		}
	}
	cout << reks(0, 0, n, m)-sub[n-1][m-1]; return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	88788 KB	Output is correct
2	Correct	28 ms	88888 KB	Output is correct
3	Correct	27 ms	88880 KB	Output is correct
4	Correct	28 ms	88772 KB	Output is correct
5	Correct	28 ms	88916 KB	Output is correct
6	Correct	28 ms	88888 KB	Output is correct
7	Correct	30 ms	88916 KB	Output is correct
8	Correct	48 ms	88916 KB	Output is correct
9	Correct	45 ms	88780 KB	Output is correct
10	Correct	53 ms	88912 KB	Output is correct
11	Correct	50 ms	88820 KB	Output is correct
12	Correct	111 ms	88908 KB	Output is correct
13	Correct	153 ms	88916 KB	Output is correct
14	Correct	79 ms	88896 KB	Output is correct
15	Correct	201 ms	88924 KB	Output is correct
16	Correct	44 ms	88860 KB	Output is correct
17	Correct	94 ms	88888 KB	Output is correct
18	Correct	520 ms	88928 KB	Output is correct
19	Correct	815 ms	88932 KB	Output is correct
20	Correct	944 ms	88932 KB	Output is correct