oj.uz

Submission #486390

# Submission time Handle Problem Language Result Execution time Memory
486390 2021-11-11T14:47:23 Z rainboy Nafta (COI15_nafta) C
100 / 100
 294 ms 84556 KB 
#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;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 668 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 668 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct
7 Correct 5 ms 3788 KB Output is correct
8 Correct 6 ms 3760 KB Output is correct
9 Correct 7 ms 3752 KB Output is correct
10 Correct 8 ms 3752 KB Output is correct
11 Correct 6 ms 3736 KB Output is correct
12 Correct 5 ms 3788 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 668 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 0 ms 588 KB Output is correct
7 Correct 5 ms 3788 KB Output is correct
8 Correct 6 ms 3760 KB Output is correct
9 Correct 7 ms 3752 KB Output is correct
10 Correct 8 ms 3752 KB Output is correct
11 Correct 6 ms 3736 KB Output is correct
12 Correct 5 ms 3788 KB Output is correct
13 Correct 279 ms 84548 KB Output is correct
14 Correct 287 ms 84548 KB Output is correct
15 Correct 294 ms 84496 KB Output is correct
16 Correct 227 ms 84556 KB Output is correct
17 Correct 252 ms 84540 KB Output is correct
18 Correct 252 ms 84532 KB Output is correct