Submission #978990

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978990	2024-05-10T05:36:25 Z	tamir1	Raisins (IOI09_raisins)	C++17	100 / 100	438 ms	53588 KB

raisins

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[51][51],dp[51][51][51][51],i,j,sum[51][51];
ll rec(ll a,ll b,ll c,ll d){
	ll &ret=dp[a][b][c][d];
	if(ret!=-1) return ret;
	if(a==c && b==d) return ret=0;
	ll val=sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
	ll i,mn=1e18;
	for(i=a;i<c;i++){
		mn=min(mn,rec(a,b,i,d)+rec(i+1,b,c,d));
	}
	for(i=b;i<d;i++){
		mn=min(mn,rec(a,b,c,i)+rec(a,i+1,c,d));
	}
	return ret=val+mn;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dp,-1,sizeof dp);
	cin >> n >> m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> a[i][j];
			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	cout << rec(1,1,n,m);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	53332 KB	Output is correct
2	Correct	9 ms	53340 KB	Output is correct
3	Correct	8 ms	53400 KB	Output is correct
4	Correct	8 ms	53340 KB	Output is correct
5	Correct	7 ms	53340 KB	Output is correct
6	Correct	8 ms	53196 KB	Output is correct
7	Correct	9 ms	53340 KB	Output is correct
8	Correct	13 ms	53340 KB	Output is correct
9	Correct	17 ms	53340 KB	Output is correct
10	Correct	21 ms	53448 KB	Output is correct
11	Correct	19 ms	53424 KB	Output is correct
12	Correct	48 ms	53336 KB	Output is correct
13	Correct	81 ms	53436 KB	Output is correct
14	Correct	27 ms	53340 KB	Output is correct
15	Correct	98 ms	53440 KB	Output is correct
16	Correct	16 ms	53340 KB	Output is correct
17	Correct	40 ms	53408 KB	Output is correct
18	Correct	221 ms	53440 KB	Output is correct
19	Correct	374 ms	53588 KB	Output is correct
20	Correct	438 ms	53448 KB	Output is correct