Submission #1198513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198513		MuhammadSaram	Nafta (COI15_nafta)	C++20	0 / 100	1 ms	1088 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],cc;
string a[M];

int main()
{
	int n,m;
	cin>>n>>m;
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		for (int j=0;j<m;j++)
			if (a[i][j]!='.')
			{
				if (i && a[i-1][j]!='.')
					col[i][j]=col[i-1][j];
			}
		for (int j=m-2;j>=0;j--)
			if (a[i][j]!='.' && col[i][j+1])
				col[i][j]=col[i][j+1];
		for (int j=0;j<m;j++)
		{
			if (a[i][j]!='.' && !col[i][j])
			{
				if (j && col[i][j-1]) col[i][j]=col[i][j-1];
				else col[i][j]=++cc;
			}
			sz[col[i][j]]+=a[i][j]-'0';
		}
	}
	for (int j=0;j<m;j++)
	{
		set<int> se;
		for (int i=0;i<n;i++)
			se.insert(col[i][j]);
		for (int j1=j;j1<m;j1++)
		{
			set<int> se1;
			for (int i=0;i<n;i++)
				if (col[i][j1] && !se1.count(col[i][j1]) && se.count(col[i][j1]))
					com[j][j1]+=sz[col[i][j1]],se1.insert(col[i][j1]);
		}
	}
	dp[0][1]=com[0][0];
	for (int i=1;i<m;i++)
		for (int k=1;k<=m;k++)
		{
			dp[i][k]=dp[i-1][k];
			for (int j=i-1;j>=0;j--)
				dp[i][k]=max(dp[i][k],com[i][i]+dp[j][k-1]-com[j][i]*(k>1));
		}
	for (int i=1;i<=m;i++)
		cout<<dp[m-1][i]<<'\n';
	
	return 0;
}

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