Submission #968682

#	Time	Username	Problem	Language	Result	Execution time	Memory
968682		NintsiChkhaidze	Nautilus (BOI19_nautilus)	C++17	66 / 100	1068 ms	2908 KiB

nautilus

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 505;
char a[N][N];
int dpold[N][N],dpnew[N][N];
vector <pii> neighbours = {{0,1}, {0,-1}, {1,0}, {-1,0}};
int n,m;

bool valid(int x,int y){
	return (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '.');
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int k;
	cin>>n>>m>>k;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
			if (a[i][j] == '.') dpold[i][j] = 1;
		}

	string s;
	cin>>s;

	map <char,pii> mp;
	mp['N'] = {-1,0};
	mp['S'] = {1,0};
	mp['E'] = {0,+1};
	mp['W'] = {0,-1};

	for (int i = 0; i < k; i++){

		for (int x = 1; x <= n; x++){
			for (int y = 1; y <= m; y++){
				if (!dpold[x][y]) continue;

				if (s[i] != '?'){
					int dx = mp[s[i]].f;
					int dy = mp[s[i]].s;
					int X = x + dx,Y = y + dy;
					if (valid(X,Y)) dpnew[X][Y] = 1;
					continue;
				}

				for (auto [dx,dy]: neighbours){
					int X = x + dx,Y = y + dy;
					if (valid(X,Y)) dpnew[X][Y] = 1;
				}

			}
		}

		for (int x=1;x<=n; x++)	
			for (int y=1;y<=m;y++)
				dpold[x][y] = dpnew[x][y],dpnew[x][y] = 0;
	}

	int ans=0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ans += dpold[i][j];
	cout<<ans;
}

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34