제출 #386328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386328		ronnith	Nafta (COI15_nafta)	C++14	100 / 100	416 ms	78932 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};

const int N = 2000;
int n, m, val[N + 1][N + 1], dp[N + 1][N + 1];
bool vis[N + 1][N + 1];
char a[N + 1][N + 1];

inline int sum(int x1, int y1, int x2, int y2) {
	return val[x2][y2] - val[x1 - 1][y2] - val[x2][y1 - 1] + val[x1 - 1][y1 - 1];
}

inline int oil(int l, int r) {
	if(r < l) return 0;
	return sum(l, l, r, r);
}

int sm, mxj, mnj;
void ff(int i, int j) {
	if(i <= 0 || i > n || j <= 0 || j > m) return;
	if(a[i][j] == '.') return;
	if(vis[i][j]) return;
	vis[i][j] = true;
	sm += (a[i][j] - '0');
	mxj = max(mxj, j);
	mnj = min(mnj, j);
	for(int d = 0;d < 4;d ++) {
		int ni = i + di[d], nj = j + dj[d];
		ff(ni, nj);
	}
}

void compute(int j, int l, int r, int min_l, int min_r) {
	int mid = (l + r) / 2;
	dp[j][mid] = INT_MAX;
	int min_mid = -1;
	for(int ld = min_l;ld <= min(min_r, mid);ld ++) {
		if(dp[j - 1][ld - 1] == -1) continue;
		int value = oil(ld + 1, mid);
		if(dp[j - 1][ld - 1] + value < dp[j][mid]) {
			dp[j][mid] = dp[j - 1][ld - 1] + value;
			min_mid = ld;
		}
	}
	if(l != mid) compute(j, l, mid - 1, min_l, min_mid);
	if(r != mid) compute(j, mid + 1, r, min_mid, min_r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			cin >> a[i][j];
		}
	}
	int total = 0;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			if(!vis[i][j] && a[i][j] != '.') {
				sm = 0, mxj = j, mnj = j;
				ff(i, j);
				val[mxj][mnj] += sm;
				total += sm;
			}
		}
	}
	for(int i = 1;i <= m;i ++) {
		for(int j = 1;j <= m;j ++) val[i][j] += (j != 1 ? val[i][j - 1] : 0);
		for(int j = 1;j <= m;j ++) val[i][j] += (i != 1 ? val[i - 1][j] : 0);
	}
	for(int j = 0;j <= m;j ++) {
		for(int i = 0;i <= m;i ++) {
			if(j == 0) dp[j][i] = oil(1, i);
			else if(j > i) dp[j][i] = -1;
		}
	}
	for(int j = 1;j <= m;j ++) {
		compute(j, j, m, 1, m);
	}
	for(int i = 1;i <= m;i ++) {
		cout << total - dp[i][m] << '\n';
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66