oj.uz

답안 #741772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741772 2023-05-14T21:09:41 Z MODDI 건포도 (IOI09_raisins) C++14
100 / 100
 253 ms 71976 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
ll mat[55][55], dp[55][55][55][55], pref[55][55];
// dp(i,j,k,l) minimum raisins to cut rectangle(i,j) up to(k,l);
ll f(int x1, int x2, int y1, int y2){
	if(x1 == x2 && y1 == y2)	return 0;
	if(dp[x1][x2][y1][y2] != -1)	return dp[x1][x2][y1][y2];
	
	ll	ans = 1e18;
	for(int i=x1; i < x2;i++){
		ans = min(ans, f(x1, i, y1, y2) + f(i+1, x2, y1, y2));
	}
	for(int i = y1; i < y2; i++){
		ans = min(ans, f(x1, x2, y1, i) + f(x1, x2, i+1, y2));
	}
	return dp[x1][x2][y1][y2] = ans + (pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]);
}
int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>mat[i][j];
	memset(dp, -1, sizeof dp);
	memset(pref, 0, sizeof pref);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] = pref[i-1][j] + pref[i][j-1] + mat[i][j] - pref[i-1][j-1];
		}
	}
	cout<<f(1, n, 1, m)<<endl;
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 71892 KB Output is correct
2 Correct 27 ms 71872 KB Output is correct
3 Correct 27 ms 71968 KB Output is correct
4 Correct 28 ms 71908 KB Output is correct
5 Correct 30 ms 71860 KB Output is correct
6 Correct 29 ms 71884 KB Output is correct
7 Correct 32 ms 71860 KB Output is correct
8 Correct 33 ms 71856 KB Output is correct
9 Correct 32 ms 71884 KB Output is correct
10 Correct 34 ms 71852 KB Output is correct
11 Correct 33 ms 71888 KB Output is correct
12 Correct 50 ms 71952 KB Output is correct
13 Correct 57 ms 71896 KB Output is correct
14 Correct 47 ms 71944 KB Output is correct
15 Correct 91 ms 71844 KB Output is correct
16 Correct 34 ms 71892 KB Output is correct
17 Correct 43 ms 71852 KB Output is correct
18 Correct 141 ms 71892 KB Output is correct
19 Correct 214 ms 71972 KB Output is correct
20 Correct 253 ms 71976 KB Output is correct