Submission #577479

#	Time	Username	Problem	Language	Result	Execution time	Memory
577479		asbsfds	Nafta (COI15_nafta)	C++14	100 / 100	325 ms	115784 KiB

nafta

#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 (stderr)

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 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66