oj.uz

답안 #1113507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113507 2024-11-16T17:03:57 Z Zflop 건포도 (IOI09_raisins) C++14
100 / 100
 216 ms 30412 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
int N,M,A[2001][2001],dp[55][55][55][55];
void solve() {
	cin >> N >> M;
	for (int i = 1; i <= N;++i)
		for (int j = 1; j <= M;++j)
			for (int x = 1; x <= N;++x)
				for (int y = 1; y <= M;++y)
					dp[i][j][x][y] = (int)1e9;
	for (int i = 1; i <= N;++i)
		for (int j = 1; j <= M;++j) {
			cin >> A[i][j];
			dp[i][j][1][1] = 0;
			A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
			}
	
	auto combine = [&] (int i,int j,int x,int y,int len_row,int len_col) {
		int sum = A[i + len_row - 1][j + len_col - 1] + A[i - 1][j - 1] - A[i + len_row - 1][j - 1] - A[i - 1][j + len_col - 1];
		if (i == x) 
			return sum + dp[i][j][len_row][y - j] + dp[x][y][len_row][len_col - (y - j)];
		return sum + dp[i][j][x - i][len_col] + dp[x][y][len_row - (x - i)][len_col];
		};
	
	for (int len_row = 1; len_row <= N;++len_row) {
		for (int len_col = 1; len_col <= M;++len_col)
			for (int i = 1; i <= N - len_row + 1;++i)
				for (int j = 1; j <= M - len_col + 1;++j) {
					for (int x = i + 1; x <= i + len_row  - 1;++x) // tai pe orizontala
						dp[i][j][len_row][len_col] = min(dp[i][j][len_row][len_col],combine(i,j,x,j,len_row,len_col));
					for (int y = j + 1; y <= j + len_col - 1;++y)
						dp[i][j][len_row][len_col] = min(dp[i][j][len_row][len_col],combine(i,j,i,y,len_row,len_col));
				}
		}
	cout << dp[1][1][N][M];
	}
// dp[a][b][x][y] - varfurile stanga sus si dreapta jos a unui dreptunghi
// sau mai usor sa il vad ca pe dp[a][b][len_row][len_col], ca sa am cv dupa ce le pot masura
int main() {
	solve();
	return 0;
	}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 1104 KB Output is correct
7 Correct 2 ms 1528 KB Output is correct
8 Correct 5 ms 3536 KB Output is correct
9 Correct 7 ms 5200 KB Output is correct
10 Correct 8 ms 6224 KB Output is correct
11 Correct 7 ms 5200 KB Output is correct
12 Correct 24 ms 11328 KB Output is correct
13 Correct 40 ms 14416 KB Output is correct
14 Correct 10 ms 6480 KB Output is correct
15 Correct 50 ms 16208 KB Output is correct
16 Correct 8 ms 5880 KB Output is correct
17 Correct 23 ms 11088 KB Output is correct
18 Correct 127 ms 23624 KB Output is correct
19 Correct 186 ms 28496 KB Output is correct
20 Correct 216 ms 30412 KB Output is correct