oj.uz

Submission #497922

# Submission time Handle Problem Language Result Execution time Memory
497922 2021-12-24T04:50:55 Z AQ0212 Nautilus (BOI19_nautilus) C++17
29 / 100
 1000 ms 716 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>

#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define ll long long int
#define pb push_back
#define pll pair < ll , ll >
#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;
 
ll inf2 = 3e18;
 
ll a[ 511 ][ 511 ], ans;
set < pll > st;
string s;
 
void check(ll x, ll y, ll v, ll sz, ll n, ll m){
	if(v == sz){
		// ans ++;
		st.insert(make_pair(x, y));
		// cout << x << " " << y << "-" << sx << " " << sy << " i:" << v << "\n";
		return;
	}
 
	if(s[ v ] == '?'){
		if(x + 1 <= n && !a[ x + 1 ][ y ])
			check(x + 1, y, v + 1, sz, n, m);
		if(x - 1 > 0 && !a[ x - 1 ][ y ])
			check(x - 1, y, v + 1, sz, n, m);
		if(y + 1 <= m && !a[ x ][ y + 1 ])
			check(x, y + 1, v + 1, sz, n, m);
		if(y - 1 > 0 && !a[ x ][ y - 1 ])
			check(x, y - 1, v + 1, sz, n, m);
 
	}else if(s[ v ] == 'S' && x + 1 <= n){
		if(!a[ x + 1 ][ y ])
			check(x + 1, y, v + 1, sz, n, m);
 
	}else if(s[ v ] == 'N' && x - 1 > 0){
		if(!a[ x - 1 ][ y ])
			check(x - 1, y, v + 1, sz, n, m);
 
	}else if(s[ v ] == 'E' && y + 1 <= m){
		if(!a[ x ][ y + 1 ])
			check(x, y + 1, v + 1, sz, n, m);
 
	}else if(s[ v ] == 'W' && y - 1 > 0){
		if(!a[ x ][ y - 1 ])
			check(x, y - 1, v + 1, sz, n, m);
 
	}
}
 
int main (){
    ll n, m, k;
	char c;
 
	cin >> n >> m >> k;
 
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cin >> c;
			if(c == '#')
				a[ i ][ j ] = 1;
		}
	}
 
	cin >> s;
 
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(a[ i ][ j ])
				continue;
 
			check(i, j, 0, k, n, m);
 
			// ll x = i, y = j, ch = 0;
			// for(int t = 0; t < k; t ++){
			// 	if(s[ t ] == 'N' && x - 1 > 0){
			// 		if(!a[ x - 1 ][ y ])
			// 			x --;
			// 		else{
			// 			ch ++;
			// 			break;
			// 		}
			// 	}else if(s[ t ] == 'S' && x + 1 <= n){
			// 		if(!a[ x + 1 ][ y ])
			// 			x ++;
			// 		else{
			// 			ch ++;
			// 			break;
			// 		}
			// 	}else if(s[ t ] == 'W' && y - 1 > 0){
			// 		if(!a[ x ][ y - 1 ])
			// 			y --;
			// 		else{
			// 			ch ++;
			// 			break;
			// 		}
			// 	}else if(s[ t ] == 'E' && y + 1 <= m){
			// 		if(!a[ x ][ y + 1 ])
			// 			y ++;
			// 		else{
			// 			ch ++;
			// 			break;
			// 		}
			// 	}
			// }
 
			// if(!ch)
			// 	ans ++;
		}
	}
 
	cout << st.size();
}
 
/*
 
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
 
3 3 3
#..
.#.
..#

*/

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 684 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 684 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Execution timed out 1077 ms 292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 684 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Execution timed out 1077 ms 292 KB Time limit exceeded
8 Halted 0 ms 0 KB -