oj.uz

Submission #379279

# Submission time Handle Problem Language Result Execution time Memory
379279 2021-03-17T20:09:38 Z penguinhacker Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 23504 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;
				for (int k = 0; k < mn; ++k) {
					c[k][mn] += cur;
					if (mx + 1 < m)
						c[k][mx + 1] -= cur;
				}
			}
	for (int i = 0; i < m; ++i)
		for (int j = i + 1; j < m; ++j)
			c[i][j] += c[i][j - 1];
	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 1 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 768 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 768 KB Output is correct
7 Correct 9 ms 2540 KB Output is correct
8 Correct 10 ms 2668 KB Output is correct
9 Correct 8 ms 3692 KB Output is correct
10 Correct 7 ms 2668 KB Output is correct
11 Correct 5 ms 2540 KB Output is correct
12 Correct 5 ms 2540 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 768 KB Output is correct
7 Correct 9 ms 2540 KB Output is correct
8 Correct 10 ms 2668 KB Output is correct
9 Correct 8 ms 3692 KB Output is correct
10 Correct 7 ms 2668 KB Output is correct
11 Correct 5 ms 2540 KB Output is correct
12 Correct 5 ms 2540 KB Output is correct
13 Execution timed out 1085 ms 23504 KB Time limit exceeded
14 Halted 0 ms 0 KB -