Submission #163101

#	Time	Username	Problem	Language	Result	Execution time	Memory
163101		TadijaSebez	Sandwich (JOI16_sandwich)	C++11	0 / 100	3 ms	660 KiB

sandwich

#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
char mat[N][N];
int NS[N][N],ZS[N][N];
int GetN(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];}
int GetZ(int xl, int xr, int yl, int yr){ return ZS[xr][yr]-ZS[xl-1][yr]-ZS[xr][yl-1]+ZS[xl-1][yl-1];}
int SZ(int xl, int xr, int yl, int yr){ return (xr-xl+1)*(yr-yl+1);}
int ans[N][N];
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf(" %c",&mat[i][j]);
			NS[i][j]=NS[i-1][j]+NS[i][j-1]-NS[i-1][j-1]+(mat[i][j]=='N');
			ZS[i][j]=ZS[i-1][j]+ZS[i][j-1]-ZS[i-1][j-1]+(mat[i][j]=='Z');
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=inf;
	int up=0;
	for(int i=0;i<n;i++)
	{
		if(i>0)
		{
			int L=0,R=m+1;
			while(mat[i][L+1]=='Z') L++;
			while(mat[i][R-1]=='N') R--;
			if(L+1!=R) break;
			up+=m;
		}
		for(int x=i+1;x<=n;x++) for(int y=1;y<=m;y++)
		{
			if(GetZ(i+1,x,y,m)==0) ans[x][y]=min(ans[x][y],up+SZ(i+1,x,y,m));
			if(GetN(i+1,x,1,y)==0) ans[x][y]=min(ans[x][y],up+SZ(i+1,x,1,y));
		}
	}
	int dw=0;
	for(int i=n+1;i>=2;i--)
	{
		if(i<=n)
		{
			int L=0,R=m+1;
			while(mat[i][L+1]=='N') L++;
			while(mat[i][R-1]=='Z') R--;
			if(L+1!=R) break;
			dw+=m;
		}
		for(int x=1;x<i;x++) for(int y=1;y<=m;y++)
		{
			if(GetN(x,i-1,y,m)==0) ans[x][y]=min(ans[x][y],dw+SZ(x,i-1,y,m));
			if(GetZ(x,i-1,1,y)==0) ans[x][y]=min(ans[x][y],dw+SZ(x,i-1,1,y));
		}
	}
	int le=0;
	for(int j=0;j<m;j++)
	{
		if(j>0)
		{
			int L=0,R=n+1;
			while(mat[L+1][j]=='Z') L++;
			while(mat[R-1][j]=='N') R--;
			if(L+1!=R) break;
			le+=n;
		}
		for(int x=1;x<=n;x++) for(int y=j+1;y<=m;y++)
		{
			if(GetN(1,x,j+1,y)==0) ans[x][y]=min(ans[x][y],le+SZ(1,x,j+1,y));
			if(GetZ(x,n,j+1,y)==0) ans[x][y]=min(ans[x][y],le+SZ(x,n,j+1,y));
		}
	}
	int ri=0;
	for(int j=m+1;j>=2;j--)
	{
		if(j<=m)
		{
			int L=0,R=n+1;
			while(mat[L+1][j]=='N') L++;
			while(mat[R-1][j]=='Z') R--;
			if(L+1!=R) break;
			ri+=n;
		}
		for(int x=1;x<=n;x++) for(int y=1;y<j;y++)
		{
			if(GetZ(1,x,y,j-1)==0) ans[x][y]=min(ans[x][y],ri+SZ(1,x,y,j-1));
			if(GetN(x,n,y,j-1)==0) ans[x][y]=min(ans[x][y],ri+SZ(x,n,y,j-1));
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ans[i][j]==inf) printf("-1 ");
			else printf("%i ",ans[i][j]*2);
		}
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:14: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:19:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&mat[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~

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