oj.uz

Submission #907861

# Submission time Handle Problem Language Result Execution time Memory
907861 2024-01-16T05:40:15 Z Trisanu_Das Nafta (COI15_nafta) C++17
100 / 100
 237 ms 75348 KB 
#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.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 5 ms 5212 KB Output is correct
9 Correct 6 ms 6492 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 4 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4564 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4700 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 5 ms 5212 KB Output is correct
9 Correct 6 ms 6492 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 4 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 135 ms 28224 KB Output is correct
14 Correct 170 ms 28296 KB Output is correct
15 Correct 237 ms 75348 KB Output is correct
16 Correct 117 ms 28068 KB Output is correct
17 Correct 113 ms 28392 KB Output is correct
18 Correct 101 ms 28196 KB Output is correct