Submission #379292

#	Time	Username	Problem	Language	Result	Execution time	Memory
379292		penguinhacker	Nafta (COI15_nafta)	C++14	100 / 100	412 ms	75500 KiB

nafta

#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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66