제출 #1200226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200226		MuhammadSaram	Nafta (COI15_nafta)	C++20	100 / 100	418 ms	170268 KiB

nafta

#include <bits/stdc++.h>

using namespace std;

const int M = 2001;

int dp[M][M],col[M][M],com[M][M],sz[M*M],mn[M*M],mx[M*M],fen[M],cc,n,m;
string a[M];

void dfs(int i,int j)
{
	col[i][j]=cc,sz[cc]+=a[i][j]-'0';
	for (int px=-1;px<=1;px++)
		for (int py=-1;py<=1;py++)
		{
			if ((px==0)==(py==0)) continue;
			int ni=i+px,nj=j+py;
			if (min(ni,nj)>=1 && ni<=n && nj<=m && !col[ni][nj] && a[ni][nj]!='.')
				dfs(ni,nj);
		}
}

void modify(int p,int x)
{
	while (p<M)
		fen[p]+=x,p+=p&-p;
}

int get(int p)
{
	int ans=0;
	while (p)
		ans+=fen[p],p^=p&-p;
	return ans;
}

void DnC(int l,int r,int i,int j,int k)
{
	if (l>r) return;
	int mid=(l+r)/2,id=i;
	dp[mid][k]=dp[i][k-1]+com[mid][mid]-com[i][mid];
	for (int x=i+1;x<=min(j,mid-1);x++)
	{
		int val=dp[x][k-1]+com[mid][mid]-com[x][mid];
		if (val>dp[mid][k])
			dp[mid][k]=val,id=x;
	}
	if (l==r) return;
	DnC(l,mid-1,i,id,k);
	DnC(mid+1,r,id,j,k);
}

int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
		cin>>a[i],a[i]='.'+a[i];
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (a[i][j]!='.' && !col[i][j])
				cc++,dfs(i,j);
	for (int i=1;i<=cc;i++) mn[i]=m,mx[i]=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			mn[col[i][j]]=min(mn[col[i][j]],j),mx[col[i][j]]=max(mx[col[i][j]],j);
	vector<int> st[m+1],en[m+1];
	for (int i=1;i<=cc;i++)
		st[mn[i]].push_back(i),en[mx[i]].push_back(i);
	for (int i=1;i<=m;i++)
	{
		for (int c:st[i])
			modify(i,sz[c]),modify(mx[c]+1,-sz[c]);
		for (int j=i;j<=m;j++)
			com[i][j]=get(j);
		for (int c:en[i])
			modify(i,-sz[c]),modify(mx[c]+1,sz[c]);
	}
	for (int i=1;i<=m;i++)
		dp[i][1]=com[i][i];
	for (int k=2;k<=m;k++)
		DnC(1,m,1,m,k);
	for (int i=1;i<=m;i++)
	{
		int ans=0;
		for (int j=1;j<=m;j++)
			ans=max(ans,dp[j][i]);
		cout<<ans<<'\n';
	}
	
	return 0;
}

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