Submission #815794

#	Time	Username	Problem	Language	Result	Execution time	Memory
815794		beaboss	Nafta (COI15_nafta)	C++14	100 / 100	362 ms	114560 KiB

nafta

// Source: https://oj.uz/problem/view/COI15_nafta

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

const int N = 2001;

int r, s;

int a[N][N];
bool vis[N][N];

vpii events[N];
int st[N];

int miny, maxy, cost;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int contr[N];
int overlap[N][N];

int dp[N][N];

int ans[N];

void compute(int l, int r, int j, int optl, int optr) {
	if (l > r) return;
	int i = (l + r) / 2;
	int cur_opt;
	int best = 0;
	
	for (int k = optl; k <= min(i, optr); k++) {
		if (dp[k][j-1] - overlap[k][i] >= best) {
			best = dp[k][j-1] - overlap[k][i];
			cur_opt = k;
		}
	}

	dp[i][j] = best + contr[i];

	ans[j] = max(dp[i][j], ans[j]);

	compute(l, i - 1, j,  optl, cur_opt);
	compute(i+1, r, j, cur_opt, optr);

}

void solve(int x, int y) {
	// cout << x << y << endl;
	miny = min(miny, y);
	maxy = max(maxy, y);
	cost += a[x][y];
	vis[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int newx = x + dx[i];
		int newy = y + dy[i];

		if (newx >= 0 && newx < r && newy >= 0 && newy < s && !vis[newx][newy] && a[newx][newy] != -1) solve(newx, newy);

	}	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// input
	cin >> r >> s;

	FOR(i, 0, r) {
		FOR(j, 0, s) {
			char inp;
			cin >> inp;
			if (inp == '.') a[i][j] = -1;
			else a[i][j] = inp - '0';
		}
	}

	// extract components
	FOR(i, 0, r) FOR(j, 0, s) {
		if (!vis[i][j] && a[i][j] != -1) {
			maxy = j;
			miny = j;
			cost = 0;
			solve(i, j);
			events[miny].pb({miny, cost});
			events[maxy+1].pb({miny, -cost});
			FOR(i, miny, maxy + 1) {
				dp[i][0] += cost;
				contr[i] += cost;
				ans[0] = max(ans[0],dp[i][0]);
			}
		}
	}

	// get overlap
	FOR(i, 0, s) {
		for (auto val: events[i]) st[val.f] += val.s;
		int cur_count = 0;
		FOR(j, 0, i + 1) {
			cur_count += st[j];
			overlap[j][i] = cur_count;
		}

	}


	cout << ans[0] << endl;
	FOR(i, 1, s) {
		compute(0, s-1, i, 0, s-1);
		cout << ans[i] << endl;
	}




}

Compilation message (stderr)

nafta.cpp: In function 'void compute(int, int, int, int, int)':
nafta.cpp:59:9: warning: 'cur_opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |  compute(l, i - 1, j,  optl, cur_opt);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66