Submission #163184

#	Time	Username	Problem	Language	Result	Execution time	Memory
163184		TadijaSebez	Sandwich (JOI16_sandwich)	C++11	0 / 100	6 ms	636 KiB

sandwich

#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
char mat[N][N],tmp1[N][N];
int n,m,id[N][N],tmp2[N][N],ans[N*N];
void rot()
{
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		tmp1[m-j+1][i]=mat[i][j];
		tmp2[m-j+1][i]=id[i][j];
	}
	swap(n,m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		mat[i][j]=tmp1[i][j];
		if(mat[i][j]=='N') mat[i][j]='Z';
		else mat[i][j]='N';
		id[i][j]=tmp2[i][j];
	}
}
bool dp[N][N];
int NS[N][N];
int Get(int xl, int xr, int yl, int yr){ return NS[xr][yr]-NS[xl-1][yr]-NS[xr][yl-1]+NS[xl-1][yl-1];}
void Solve()
{
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) NS[i][j]=NS[i-1][j]+NS[i][j-1]-NS[i-1][j-1]+(mat[i][j]=='N');
	dp[1][1]=1;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i!=1 || j!=1)
	{
		dp[i][j]=0;
		if(i!=1 && dp[i-1][j])
		{
			int L=j-1,R=m+1;
			while(L<m && mat[i-1][L+1]=='Z') L++;
			while(R>j && mat[i-1][R-1]=='N') R--;
			if(L+1==R) dp[i][j]=1;
		}
		if(j!=1 && dp[i][j-1])
		{
			int L=i-1,R=n+1;
			while(L<n && mat[L+1][j-1]=='Z') L++;
			while(R>i && mat[R-1][j-1]=='N') R--;
			if(L+1==R) dp[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		for(int k=j;k>=1;k--)
		{
			int bot=1,top=i,mid,sol=-1;
			while(top>=bot)
			{
				mid=top+bot>>1;
				if(Get(mid,i,k,j)==0) sol=mid,top=mid-1;
				else bot=mid+1;
			}
			if(sol!=-1 && dp[sol][k]) ans[id[i][j]]=min(ans[id[i][j]],(j-k+1)*(i-sol+1)+n*(k-1)+m*(sol-1)-(k-1)*(sol-1));
		}
	}
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=(i-1)*m+j;
	for(int i=1;i<=n*m;i++) ans[i]=inf;
	for(int i=1;i<=n;i++) scanf("%s",mat[i]+1);
	for(int i=1;i<=4;i++) Solve(),rot();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ans[(i-1)*m+j]==inf) printf("-1 ");
			else printf("%i ",ans[(i-1)*m+j]*2);
		}
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

sandwich.cpp: In function 'void Solve()':
sandwich.cpp:55:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
sandwich.cpp:68:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",mat[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65