제출 #486390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486390		rainboy	Nafta (COI15_nafta)	C11	100 / 100	294 ms	84556 KiB

nafta

#include <stdio.h>
#include <string.h>

#define N	2000
#define M	2000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ds[N * M], ww[N * M], ll[N * M], rr[N * M];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, ww[j] += ww[i], ll[j] = min(ll[j], ll[i]), rr[j] = max(rr[j], rr[i]);
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, ww[i] += ww[j], ll[i] = min(ll[i], ll[j]), rr[i] = max(rr[i], rr[j]);
	}
}

int dp[M + 2], dq[M + 2], www[M + 2][M + 2];

void solve(int l, int r, int l_, int r_) {
	int m, m_, x_, x, i;

	if (l > r)
		return;
	m = (l + r) / 2, m_ = -1, x_ = INF;
	for (i = l_; i <= r_; i++)
		if (i <= m && x_ > (x = dp[i] + www[i][m]))
			x_ = x, m_ = i;
	dq[m] = x_;
	solve(l, m - 1, l_, m_), solve(m + 1, r, m_, r_);
}

int main() {
	static char cc[N][M + 1];
	int n, m, k, h, i, j, l, r, w;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			ds[i * m + j] = -1, ll[i * m + j] = rr[i * m + j] = j + 1, ww[i * m + j] = cc[i][j] == '.' ? 0 : cc[i][j] - '0';
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			if (cc[i][j] == '.')
				continue;
			if (i > 0 && cc[i - 1][j] != '.')
				join((i - 1) * m + j, i * m + j);
			if (j > 0 && cc[i][j - 1] != '.')
				join(i * m + j - 1, i * m + j);
		}
	w = 0;
	for (h = 0; h < n * m; h++)
		if (ds[h] < 0)
			w += ww[h], www[ll[h] - 1][rr[h] + 1] += ww[h];
	for (l = 0; l <= m; l++)
		for (r = l + 1; r <= m + 1; r++)
			www[l][r] += www[l][r - 1];
	for (l = m; l >= 0; l--)
		for (r = l + 1; r <= m + 1; r++)
			www[l][r] += www[l + 1][r];
	for (r = 0; r <= m + 1; r++)
		dp[r] = www[0][r];
	for (k = 1; k <= m; k++) {
		solve(0, m + 1, 0, m + 1);
		memcpy(dp, dq, (m + 2) * sizeof *dq);
		printf("%d\n", w - dp[m + 1]);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

nafta.c: In function 'main':
nafta.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
nafta.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

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