oj.uz

답안 #659805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659805 2022-11-19T09:43:08 Z Tob 건포도 (IOI09_raisins) C++14
100 / 100
 659 ms 83016 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 57;

int n, m;
ll mat[N][N], ps[N][N];
ll dp[N][N][N][N];

ll f(int a1, int b1, int a2, int b2) {
	return ps[a2][b2] - ps[a1-1][b2] - ps[a2][b1-1] + ps[a1-1][b1-1];
}

ll DP(int a1, int b1, int a2, int b2) {
	if (dp[a1][b1][a2][b2] != -1) return dp[a1][b1][a2][b2];
	if (a1 == a2 && b1 == b2) {
		dp[a1][b1][a2][b2] = 0;
		return 0;
	}
	ll mn = 1e18;
	for (int i = a1; i < a2; i++) {
		mn = min(mn, DP(a1, b1, i, b2) + DP(i+1, b1, a2, b2));
	}
	for (int i = b1; i < b2; i++) {
		mn = min(mn, DP(a1, b1, a2, i) + DP(a1, i+1, a2, b2));
	}
	dp[a1][b1][a2][b2] = mn + f(a1, b1, a2, b2);
	return dp[a1][b1][a2][b2];
}

int main () {
	memset(dp, -1, sizeof dp);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + mat[i][j];
		}
	}
	
	cout << DP(1, 1, n, m);
	
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 82892 KB Output is correct
2 Correct 31 ms 82892 KB Output is correct
3 Correct 33 ms 82972 KB Output is correct
4 Correct 33 ms 82904 KB Output is correct
5 Correct 37 ms 82932 KB Output is correct
6 Correct 35 ms 82856 KB Output is correct
7 Correct 32 ms 82876 KB Output is correct
8 Correct 46 ms 82920 KB Output is correct
9 Correct 42 ms 82920 KB Output is correct
10 Correct 50 ms 82892 KB Output is correct
11 Correct 50 ms 82920 KB Output is correct
12 Correct 87 ms 82952 KB Output is correct
13 Correct 121 ms 82952 KB Output is correct
14 Correct 56 ms 82920 KB Output is correct
15 Correct 147 ms 82960 KB Output is correct
16 Correct 46 ms 83016 KB Output is correct
17 Correct 79 ms 82956 KB Output is correct
18 Correct 370 ms 82968 KB Output is correct
19 Correct 549 ms 82972 KB Output is correct
20 Correct 659 ms 82972 KB Output is correct