oj.uz

Submission #386328

# Submission time Handle Problem Language Result Execution time Memory
386328 2021-04-06T11:48:19 Z ronnith Nafta (COI15_nafta) C++14
100 / 100
 416 ms 78932 KB 
#include <bits/stdc++.h>

using namespace std;

const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};

const int N = 2000;
int n, m, val[N + 1][N + 1], dp[N + 1][N + 1];
bool vis[N + 1][N + 1];
char a[N + 1][N + 1];

inline int sum(int x1, int y1, int x2, int y2) {
	return val[x2][y2] - val[x1 - 1][y2] - val[x2][y1 - 1] + val[x1 - 1][y1 - 1];
}

inline int oil(int l, int r) {
	if(r < l) return 0;
	return sum(l, l, r, r);
}

int sm, mxj, mnj;
void ff(int i, int j) {
	if(i <= 0 || i > n || j <= 0 || j > m) return;
	if(a[i][j] == '.') return;
	if(vis[i][j]) return;
	vis[i][j] = true;
	sm += (a[i][j] - '0');
	mxj = max(mxj, j);
	mnj = min(mnj, j);
	for(int d = 0;d < 4;d ++) {
		int ni = i + di[d], nj = j + dj[d];
		ff(ni, nj);
	}
}

void compute(int j, int l, int r, int min_l, int min_r) {
	int mid = (l + r) / 2;
	dp[j][mid] = INT_MAX;
	int min_mid = -1;
	for(int ld = min_l;ld <= min(min_r, mid);ld ++) {
		if(dp[j - 1][ld - 1] == -1) continue;
		int value = oil(ld + 1, mid);
		if(dp[j - 1][ld - 1] + value < dp[j][mid]) {
			dp[j][mid] = dp[j - 1][ld - 1] + value;
			min_mid = ld;
		}
	}
	if(l != mid) compute(j, l, mid - 1, min_l, min_mid);
	if(r != mid) compute(j, mid + 1, r, min_mid, min_r);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			cin >> a[i][j];
		}
	}
	int total = 0;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= m;j ++) {
			if(!vis[i][j] && a[i][j] != '.') {
				sm = 0, mxj = j, mnj = j;
				ff(i, j);
				val[mxj][mnj] += sm;
				total += sm;
			}
		}
	}
	for(int i = 1;i <= m;i ++) {
		for(int j = 1;j <= m;j ++) val[i][j] += (j != 1 ? val[i][j - 1] : 0);
		for(int j = 1;j <= m;j ++) val[i][j] += (i != 1 ? val[i - 1][j] : 0);
	}
	for(int j = 0;j <= m;j ++) {
		for(int i = 0;i <= m;i ++) {
			if(j == 0) dp[j][i] = oil(1, i);
			else if(j > i) dp[j][i] = -1;
		}
	}
	for(int j = 1;j <= m;j ++) {
		compute(j, j, m, 1, m);
	}
	for(int i = 1;i <= m;i ++) {
		cout << total - dp[i][m] << '\n';
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 2 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 2 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 9 ms 4716 KB Output is correct
8 Correct 11 ms 4716 KB Output is correct
9 Correct 11 ms 5616 KB Output is correct
10 Correct 8 ms 4716 KB Output is correct
11 Correct 9 ms 4716 KB Output is correct
12 Correct 9 ms 4716 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 2 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 9 ms 4716 KB Output is correct
8 Correct 11 ms 4716 KB Output is correct
9 Correct 11 ms 5616 KB Output is correct
10 Correct 8 ms 4716 KB Output is correct
11 Correct 9 ms 4716 KB Output is correct
12 Correct 9 ms 4716 KB Output is correct
13 Correct 298 ms 43644 KB Output is correct
14 Correct 360 ms 43536 KB Output is correct
15 Correct 416 ms 78932 KB Output is correct
16 Correct 287 ms 43460 KB Output is correct
17 Correct 304 ms 43408 KB Output is correct
18 Correct 284 ms 43412 KB Output is correct