oj.uz

Submission #379292

# Submission time Handle Problem Language Result Execution time Memory
379292 2021-03-17T21:05:06 Z penguinhacker Nafta (COI15_nafta) C++14
100 / 100
 412 ms 75500 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 2000;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int n, m, c[mxN][mxN];
string g[mxN];

int cur, mn, mx;
bool vis[mxN][mxN];
void dfs(int i, int j) {
	vis[i][j] = 1;
	cur += g[i][j] - '0';
	mn = min(mn, j);
	mx = max(mx, j);
	for (int k = 0; k < 4; ++k) {
		int a = i + dx[k], b = j + dy[k];
		if (0 <= a && a < n && 0 <= b && b < m && !vis[a][b] && g[a][b] != '.')
			dfs(a, b);
	}
}

vector<int> dp, ndp;
void solve(int l, int r, int ql, int qr) {
	if (l > r)
		return;
	int mid = (l + r) / 2;
	pair<int, int> best = {-1, -1};
	for (int i = ql; i <= min(qr, mid); ++i)
		best = max(best, {dp[i] + c[i][mid], i});
	ndp[mid] = best.first;
	solve(l, mid - 1, ql, best.second);
	solve(mid + 1, r, best.second, qr);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> g[i];
	dp.resize(m), ndp.resize(m);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (!vis[i][j] && g[i][j] != '.') {
				cur = 0, mn = 1e9, mx = -1;
				dfs(i, j);
				for (int k = mn; k <= mx; ++k) {
					dp[k] += cur;
					c[0][k] += cur;
					c[mn][k] -= cur;
				}
			}
	for (int j = 0; j < m; ++j)
		for (int i = 1; i < m; ++i)
			c[i][j] += c[i - 1][j];
	cout << *max_element(dp.begin(), dp.end()) << "\n";
	for (int i = 2; i <= m; ++i) {
		solve(0, m - 1, 0, m - 1);
		swap(dp, ndp);
		cout << *max_element(dp.begin(), dp.end()) << "\n";
	}
	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 7 ms 2812 KB Output is correct
8 Correct 7 ms 2796 KB Output is correct
9 Correct 8 ms 3948 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 5 ms 2796 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 7 ms 2812 KB Output is correct
8 Correct 7 ms 2796 KB Output is correct
9 Correct 8 ms 3948 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 5 ms 2796 KB Output is correct
13 Correct 304 ms 28416 KB Output is correct
14 Correct 374 ms 28396 KB Output is correct
15 Correct 412 ms 75500 KB Output is correct
16 Correct 282 ms 28216 KB Output is correct
17 Correct 256 ms 28328 KB Output is correct
18 Correct 252 ms 28140 KB Output is correct