Submission #375797

#	Time	Username	Problem	Language	Result	Execution time	Memory
375797		8e7	Nafta (COI15_nafta)	C++14	100 / 100	321 ms	109676 KiB

nafta

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#define ll long long
#define maxn 2005
#define pii pair<int, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int n, m;
int dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
char a[maxn][maxn];
int dp[2][maxn], w[maxn][maxn];
bool found[maxn][maxn];

int lef, rig, cur;
void dfs(int x, int y) {
	lef = min(lef, y);
	rig = max(rig, y);
	found[x][y] = 1;
	cur += a[x][y] - '0';
	for (int k = 0;k < 4;k++) {
		int nx = x + dir[k][0], ny = y + dir[k][1];
		if (nx > 0 && nx <= n && ny > 0 && ny <= m) {
			if (a[nx][ny] != '.' && !found[nx][ny]) {
				dfs(nx, ny);
			}
		}
	}
}

void solve(int l, int r, int ql, int qr) { //[l, r), [ql, qr)
	if (r <= l || qr <= ql) return;
	if (qr - ql == 1) {
		for (int i = l;i < r;i++) {
			dp[1][i] = dp[0][ql] + w[ql + 1][i] - w[i + 1][i + 1];
		}
		return;
	}
	int mid = (l + r) / 2;
	int ind = ql;
	for (int i = ql;i < min(mid, qr);i++) {
		int val = dp[0][i] + w[i + 1][mid] - w[mid + 1][mid + 1];
		if (val > dp[1][mid]) {
			dp[1][mid] = val, ind = i;
		}
	}
	solve(l, mid, ql, ind + 1);
	solve(mid + 1, r, ind, qr);
}
int main() {
	io
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		string s;
		cin >> s;
		for (int j = 1;j <= m;j++) {
			a[i][j] = s[j - 1];
		}
	}
	//int tot = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			if (!found[i][j] && a[i][j] != '.') {
				//cout << i << " " << j << "  " << a[i][j] << endl;
				lef = 1<<30, rig = -1, cur = 0;
				dfs(i, j);
				//cout << lef << " " << rig << " " << cur << endl;
				w[lef][rig] += cur;
				//tot += cur;
			}
		}
	}

	for (int i = m;i >= 0;i--) {
		for (int j = m;j >= 0;j--) w[i][j] += w[i][j + 1];
		if (i < m) {
			for (int j = 0;j <= m;j++) w[i][j] += w[i + 1][j];
		}
	}
	for (int i = 0;i <= m;i++) {
		for (int j = 0;j < i;j++) w[i][j] = -(1<<30);
	}


	for (int i = 1;i <= m;i++) {
		int ans = 0;
		if (i > 1) {
			solve(i, m + 1, i - 1, m + 1);
		} else {
			for (int j = 1;j <= m;j++) dp[1][j] = w[0][j] - w[j + 1][j + 1];
		}
		//solve(i, m + 1, i - 1, m + 1);
		for (int j = i;j <= m;j++) {
			ans = max(ans, dp[1][j]);
			//cout << dp[1][j] << " ";
		}
		//cout << endl;
		for (int j = i;j <= m;j++) dp[0][j] = dp[1][j], dp[1][j] = 0;
		cout << ans << endl;
	}

}
/*
w[i][j] is sum of every segment with l >= i, r >= j;

5 5
...3.
....1
..0.3
489..
.....

3 5
999.1
.....
1.999


5 5
.27..
7.063
....7
78...
8...2
 */

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