제출 #1310152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310152		Jawad_Akbar_JJ	Nafta (COI15_nafta)	C++20	34 / 100	1097 ms	36656 KiB

nafta

#include <iostream>
#include <queue>

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];

void bfs(int r, int c){
	queue<pair<int, int>> Q;
	Q.push({r, c});
	seen[r][c] = 1;

	while (Q.size() > 0){
		auto [i, j] = Q.front();
		Q.pop();
		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.push({i-1, j});
		if (i + 1 <= n and seen[i+1][j] == 0)
			seen[i+1][j] = 1, Q.push({i+1, j});
		if (j - 1 > 0 and seen[i][j-1] == 0)
			seen[i][j-1] = 1, Q.push({i, j-1});
		if (j + 1 <= m and seen[i][j+1] == 0)
			seen[i][j+1] = 1, Q.push({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;
	}
	// cout<<mid<<" "<<bst<<" "<<mx<<endl;
	dp[mid][k] = mx;
	solve(st, mid - 1, l, bst, k);
	solve(mid + 1, en, bst, r, k);
}

int main(){
	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=Mn;k<=Mx;k++)
					for (int l=k;l<=Mx;l++)
						Cst[k][l] += 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);

	int Max = 0;
	for (int k=2;k<=m;k++){
		for (int i=k;i<=m;i++)
			for (int j=1;j<i;j++)
				dp[i][k] = max(dp[i][k], dp[j][k-1] + Cst[i][i] - Cst[j][i]);
	}
	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: 0 / 66