Submission #1310155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310155		Jawad_Akbar_JJ	Nafta (COI15_nafta)	C++20	100 / 100	260 ms	83940 KiB

nafta

#include <iostream>

using namespace std;
const int N = 8<<8;
int dp[N][N], Cst[N][N], seen[N][N], Mn, Mx, Sm, n, m;
string s[N];
pair<int, int> Q[N * N];

void bfs(int r, int c){
	int st = 1, en = 1;
	Q[en++] = {r, c};
	seen[r][c] = 1;

	while (st < en){
		auto [i, j] = Q[st++];
		if (s[i][j] == '.')
			continue;

		Mn = min(Mn, j);
		Mx = max(Mx, j);

		Sm += s[i][j] - '0';
		if (i - 1 > 0 and seen[i-1][j] == 0)
			seen[i-1][j] = 1, Q[en++] = {i-1, j};
		if (i + 1 <= n and seen[i+1][j] == 0)
			seen[i+1][j] = 1, Q[en++] = {i+1, j};
		if (j - 1 > 0 and seen[i][j-1] == 0)
			seen[i][j-1] = 1, Q[en++] = {i, j-1};
		if (j + 1 <= m and seen[i][j+1] == 0)
			seen[i][j+1] = 1, Q[en++] = {i, j+1};
	}
}

void solve(int st, int en, int l, int r, int k){
	if (st > en)
		return;
	int bst = l, mx = 0, mid = (st + en) / 2;
	for (int i=l;i<=min(mid - 1, r);i++){
		if (dp[i][k-1] + Cst[mid][mid] - Cst[i][mid] > mx)
			mx = dp[i][k-1] + Cst[mid][mid] - Cst[i][mid], bst = i;
	}
	dp[mid][k] = mx;
	solve(st, mid - 1, l, bst, k);
	solve(mid + 1, en, bst, r, k);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m;

	for (int i=1;i<=n;i++){
		cin>>s[i];
		s[i] = '0' + s[i];
	}

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (seen[i][j] == 0){
				Mn = Mx = j, Sm = 0;
				bfs(i, j);
				if (Sm == 0)
					continue;
				Cst[Mn][1] += Sm;
				Cst[Mn][Mx + 1] -= Sm;
			}
		}
	}

	for (int k : {0, 1}){
		for (int i=1;i<N;i++)
			for (int j=1;j<N;j++)
				Cst[i][j] += Cst[i][j-1] * (1 - k) + Cst[i-1][j] * k;
	}
	for (int i=1;i<N;i++)
		dp[i][1] = Cst[i][i];

	for (int k=2;k<=m;k++)
		solve(1, m, 1, m, k);

	for (int i=1;i<=m;i++){
		for (int j=1;j<=m;j++)
			dp[m][i] = max(dp[m][i], dp[j][i]);
		cout<<dp[m][i]<<'\n';
	}
}

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