oj.uz

Submission #260314

# Submission time Handle Problem Language Result Execution time Memory
260314 2020-08-10T05:05:33 Z arnold518 Nautilus (BOI19_nautilus) C++14
29 / 100
 2 ms 1920 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int MAXM = 5000;

int R, C, M;
char S[MAXN+10][MAXN+10];
char A[MAXM+10];
ll B[MAXN+10][MAXN+10];
ll D[MAXN+10][MAXN/60+10][MAXM+10];

int main()
{
	scanf("%d%d%d", &R, &C, &M);
	for(int i=1; i<=R; i++) scanf("%s", S[i]+1);
	scanf("%s", A+1);

	for(int i=1; i<=R; i++) for(int j=1; j<=C; j++) if(S[i][j]=='.') B[i][j/60]|=(1ll<<(j%60));
	for(int i=1; i<=R; i++) for(int j=0; j<=C/60; j++) D[i][j][0]=B[i][j];

	for(int p=1; p<=M; p++)
	{
		if(A[p]=='N')
		{
			for(int i=1; i<R; i++) for(int j=0; j<=C/60; j++)
			{
				D[i][j][p]=D[i+1][j][p-1];
				D[i][j][p]&=B[i][j];
			}
		}
		if(A[p]=='S')
		{
			for(int i=2; i<=R; i++) for(int j=0; j<=C/60; j++)
			{
				D[i][j][p]=D[i-1][j][p-1];
				D[i][j][p]&=B[i][j];
			}	
		}
		if(A[p]=='E')
		{
			for(int i=1; i<=R; i++)
			{
				for(int j=C/60; j>=0; j--)
				{
					D[i][j][p]=D[i][j][p-1]<<1;
					D[i][j][p]&=((1ll<<60)-1);
					if(j!=0 && (D[i][j-1][p-1]&(1ll<<59))) D[i][j][p]|=1;
					D[i][j][p]&=B[i][j];
				}
			}
		}
		if(A[p]=='W')
		{
			for(int i=1; i<=R; i++)
			{
				for(int j=0; j<=C/60; j++)
				{
					D[i][j][p]=D[i][j][p-1]>>1;
					if(j!=C/60 && (D[i][j+1][p-1]&1)) D[i][j][p]|=(1ll<<59);
					D[i][j][p]&=B[i][j];
				}
			}
		}
		if(A[p]=='?')
		{
			for(int i=1; i<=R; i++) for(int j=0; j<=C/60; j++)
			{
				if(i!=R) D[i][j][p]|=D[i+1][j][p-1];
				if(i!=1) D[i][j][p]|=D[i-1][j][p-1];
			}
			for(int i=1; i<=R; i++)
			{
				for(int j=C/60; j>=0; j--)
				{
					int t;
					t=D[i][j][p-1]<<1;
					t&=((1ll<<60)-1);
					if(j!=0 && (D[i][j-1][p-1]&(1ll<<59))) t|=1;
					D[i][j][p]|=t;
				}
			}
			for(int i=1; i<=R; i++)
			{
				for(int j=0; j<=C/60; j++)
				{
					int t;
					t=D[i][j][p-1]>>1;
					if(j!=C/60 && (D[i][j+1][p-1]&1)) t|=(1ll<<59);
					t&=B[i][j];
					D[i][j][p]|=t;
				}
			}
			for(int i=1; i<=R; i++) for(int j=0; j<=C/60; j++) D[i][j][p]&=B[i][j];
		}
	}
	int ans=0;
	for(int i=1; i<=R; i++) for(int j=0; j<=C/60; j++) ans+=__builtin_popcountll(D[i][j][M]);
	printf("%d\n", ans);
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &R, &C, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=R; i++) scanf("%s", S[i]+1);
                          ~~~~~^~~~~~~~~~~~~~
nautilus.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A+1);
  ~~~~~^~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1920 KB Output is correct
8 Incorrect 1 ms 1920 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1920 KB Output is correct
8 Incorrect 1 ms 1920 KB Output isn't correct
9 Halted 0 ms 0 KB -