oj.uz

Submission #375797

# Submission time Handle Problem Language Result Execution time Memory
375797 2021-03-10T02:30:04 Z 8e7 Nafta (COI15_nafta) C++14
100 / 100
 321 ms 109676 KB 
//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.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 2 ms 876 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 756 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 2 ms 876 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 756 KB Output is correct
7 Correct 6 ms 3052 KB Output is correct
8 Correct 8 ms 3068 KB Output is correct
9 Correct 9 ms 4972 KB Output is correct
10 Correct 6 ms 3052 KB Output is correct
11 Correct 6 ms 3052 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct

Subtask #3
66.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 2 ms 876 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 756 KB Output is correct
7 Correct 6 ms 3052 KB Output is correct
8 Correct 8 ms 3068 KB Output is correct
9 Correct 9 ms 4972 KB Output is correct
10 Correct 6 ms 3052 KB Output is correct
11 Correct 6 ms 3052 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 196 ms 23916 KB Output is correct
14 Correct 248 ms 27884 KB Output is correct
15 Correct 321 ms 109676 KB Output is correct
16 Correct 158 ms 28012 KB Output is correct
17 Correct 171 ms 27884 KB Output is correct
18 Correct 171 ms 28012 KB Output is correct