oj.uz

Submission #577479

# Submission time Handle Problem Language Result Execution time Memory
577479 2022-06-14T20:00:21 Z asbsfds Nafta (COI15_nafta) C++14
100 / 100
 325 ms 115784 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2010;
const int inf = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int n, m;
char niz[maxn][maxn];
int dp[maxn][maxn];
int bio[maxn][maxn];
int mini[maxn * maxn], maxi[maxn * maxn], sum[maxn * maxn];
int r[maxn], s[maxn];
int loga[maxn];
int cost[maxn][maxn];
vector< pair<int, int> > events[maxn];

void update(int x, int val) {
	for (x++; x < maxn; x += x & -x)
		loga[x] += val;
}

int query(int x) {
	int out = 0;
	for (x++; x > 0; x -= x & -x)
		out += loga[x];
	return out;
}

int t = 0;
void dfs(int x, int y) {
	//printf("dfsing: %d %d\n", x, y);
	bio[x][y] = t;
	sum[t] += niz[x][y] - '0';
	mini[t] = min(mini[t], y);
	maxi[t] = max(maxi[t], y);
	
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
		if (bio[tx][ty] == -1 && niz[tx][ty] != '.') dfs(tx, ty);
	}
}

void solve(int k, int l, int r, int ca, int cb) {
	if (l > r) return;
	int mid = (l + r) / 2;
	
	dp[k][mid] = -inf;
	int ind = -1;
	for (int i = ca; i <= cb; i++) {
		if (i >= mid) break;
		if (dp[k - 1][i] + cost[i][mid] > dp[k][mid]) {
			dp[k][mid] = dp[k - 1][i] + cost[i][mid];
			ind = i;
		}
	}
	
	solve(k, l, mid - 1, ca, ind);
	solve(k, mid + 1, r, ind, cb);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", niz+i);
	
	memset(mini, inf, sizeof mini);
	memset(bio, -1, sizeof bio);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (niz[i][j] != '.' && bio[i][j] == -1) {
				dfs(i, j); t++;
				//printf("found component\n");
			}
		}
	}
	
	for (int i = 0; i < t; i++) {
		//printf("%d - %d --> %d\n", mini[i], maxi[i], sum[i]);
		events[mini[i] + 1].push_back({mini[i] + 1, sum[i]});
		events[maxi[i] + 2].push_back({mini[i] + 1, -sum[i]});
	}
	
	for (int i = 1; i <= m; i++) {
		for (auto iter : events[i]) {
			update(0, iter.second);
			update(iter.first, -iter.second);
		}
			
		for (int j = 0; j < i; j++)
			cost[j][i] = query(j);
	}
	
	for (int k = 1; k <= m; k++) {
		solve(k, 1, m, 0, m);
	}
	
	for (int i = 1; i <= m; i++) {
		int maxi = 0;
		for (int j = 0; j <= m; j++) 
			maxi = max(maxi, dp[i][j]);
		printf("%d\n", maxi);
	}
	return 0;
}

Compilation message

nafta.cpp: In function 'int main()':
nafta.cpp:69:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[2010]' [-Wformat=]
   69 |   scanf("%s", niz+i);
      |          ~^   ~~~~~
      |           |      |
      |           char*  char (*)[2010]
nafta.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
nafta.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%s", niz+i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32560 KB Output is correct
2 Correct 13 ms 32496 KB Output is correct
3 Correct 16 ms 32464 KB Output is correct
4 Correct 13 ms 32484 KB Output is correct
5 Correct 13 ms 32488 KB Output is correct
6 Correct 14 ms 32440 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32560 KB Output is correct
2 Correct 13 ms 32496 KB Output is correct
3 Correct 16 ms 32464 KB Output is correct
4 Correct 13 ms 32484 KB Output is correct
5 Correct 13 ms 32488 KB Output is correct
6 Correct 14 ms 32440 KB Output is correct
7 Correct 18 ms 35988 KB Output is correct
8 Correct 18 ms 35840 KB Output is correct
9 Correct 19 ms 36684 KB Output is correct
10 Correct 17 ms 35768 KB Output is correct
11 Correct 18 ms 35668 KB Output is correct
12 Correct 17 ms 35608 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32560 KB Output is correct
2 Correct 13 ms 32496 KB Output is correct
3 Correct 16 ms 32464 KB Output is correct
4 Correct 13 ms 32484 KB Output is correct
5 Correct 13 ms 32488 KB Output is correct
6 Correct 14 ms 32440 KB Output is correct
7 Correct 18 ms 35988 KB Output is correct
8 Correct 18 ms 35840 KB Output is correct
9 Correct 19 ms 36684 KB Output is correct
10 Correct 17 ms 35768 KB Output is correct
11 Correct 18 ms 35668 KB Output is correct
12 Correct 17 ms 35608 KB Output is correct
13 Correct 263 ms 87496 KB Output is correct
14 Correct 296 ms 79168 KB Output is correct
15 Correct 325 ms 115784 KB Output is correct
16 Correct 229 ms 77516 KB Output is correct
17 Correct 278 ms 69880 KB Output is correct
18 Correct 234 ms 69704 KB Output is correct