제출 #978990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978990		tamir1	건포도 (IOI09_raisins)	C++17	100 / 100	438 ms	53588 KiB

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 / 100