oj.uz

Submission #375795

# Submission time Handle Problem Language Result Execution time Memory
375795 2021-03-10T02:29:39 Z 8e7 Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 28024 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) {
			for (int j = i;j <= m;j++) {
				for (int k = i - 1;k < j;k++) dp[1][j] = max(dp[1][j], dp[0][k] + w[k + 1][j] - w[j + 1][j + 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 1 ms 876 KB Output is correct
4 Correct 1 ms 876 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 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 12 ms 3180 KB Output is correct
8 Correct 13 ms 3180 KB Output is correct
9 Correct 16 ms 5100 KB Output is correct
10 Correct 13 ms 3180 KB Output is correct
11 Correct 16 ms 3180 KB Output is correct
12 Correct 14 ms 3180 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 876 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 12 ms 3180 KB Output is correct
8 Correct 13 ms 3180 KB Output is correct
9 Correct 16 ms 5100 KB Output is correct
10 Correct 13 ms 3180 KB Output is correct
11 Correct 16 ms 3180 KB Output is correct
12 Correct 14 ms 3180 KB Output is correct
13 Execution timed out 1072 ms 28024 KB Time limit exceeded
14 Halted 0 ms 0 KB -