oj.uz

답안 #978990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
978990 2024-05-10T05:36:25 Z tamir1 건포도 (IOI09_raisins) C++17
100 / 100
 438 ms 53588 KB 
#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

# 결과 실행 시간 메모리 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