Submission #593704

#TimeUsernameProblemLanguageResultExecution timeMemory
593704nguyentuNautilus (BOI19_nautilus)C++14
0 / 100
9 ms9556 KiB
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; #define ii pair<int , int> #define iv pair<ii , ii> #define iii pair<int , ii> #define fi first #define se second #define int long long const int inf = 1e18 + 7; const int MAX_N = 5e2 + 7; const int MOD = 1e9 + 7; char a[MAX_N][MAX_N]; int f[MAX_N][MAX_N][100]; char s[5007]; signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n , m , l; cin >> n >> m >> l; //subtask 1&2 if (n <= 100 && m <= 100 && l <= 100) { for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { cin >> a[i][j]; } } for (int i = 1 ; i <= l ; i++) { cin >> s[i]; } for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { if (a[i][j] != '#') { f[i][j][0] = 1; } } } for (int h = 1 ; h <= l ; h++) { for (int i = 1 ; i <= n ;i ++) { for (int j = 1 ; j <= m ; j++) { if (a[i][j] == '#') continue;; if (s[h] == 'W' && j < m) { f[i][j][h] = f[i][j + 1][h - 1]; } if (s[h] == 'N' && i < n) { f[i][j][h] = f[i + 1][j][h - 1]; } if (s[h] == 'E' && 1 < j) { f[i][j][h] = f[i][j - 1][h - 1]; } if (s[h] == 'S' && 1 < i) { f[i][j][h] = f[i - 1][j][h - 1]; } if (s[h] == '?') { if (j < m && f[i][j + 1][h - 1]) f[i][j][h] = f[i][j + 1][h - 1]; if (i < n && f[i + 1][j][h - 1]) f[i][j][h] = f[i + 1][j][h - 1]; if (1 < j && f[i][j - 1][h - 1]) f[i][j][h] = f[i][j - 1][h - 1]; if (1 < i && f[i - 1][j][h - 1]) f[i][j][h] = f[i - 1][j][h - 1]; } } } } int ans = 0; int cnt = 0; for (int i = 1 ; i <= n ;i ++) { for (int j = 1 ; j <= m ; j++) { if (f[i][j][l]) { ans++; } //cout << f[i][j][l] << " "; } //cout << '\n'; } cout << ans; } else { //subtask 3 bitset<5007> f[2][MAX_N]; bitset<5007> d[MAX_N]; for (int i = 0 ; i < n ; i++) { d[i].flip(); f[1][i].flip(); for (int j = 0 ; j < m ; j++) { cin >> a[i][j]; if (a[i][j] == '#') { d[i][j].flip(); f[1][i][j].flip(); } } } for (int i = 0 ; i < l ; i++) { cin >> s[i]; } for (int i = 0 ; i < l ; i++) { int now = i & 1; int prev = now ^ 1; for (int j = 0 ; j < n ; j++) { if (s[i] == 'W') { f[now][j] = f[prev][j] << 1; } if (s[i] == 'E') { f[now][j] = f[prev][j] >> 1; } if (s[i] == 'S') { f[now][j] = f[prev][j - 1]; } if (s[i] == 'N') { f[now][j] = f[prev][j + 1]; } if (s[i] == '?') { f[now][j] |= f[prev][j - 1]; f[now][j] |= f[prev][j + 1]; f[now][j] |= (f[prev][j] >> 1); f[now][j] |= (f[prev][j] << 1); } f[now][j] = f[now][j] & d[j]; } for (int j = 0 ; j < n ; j++) { f[prev][j] = f[now][j]; } } int ans = 0; for (int i = 0 ; i < n ; i++) { for (int j = 0 ; j < m ; j++) { if (f[(l - 1) & 1][i][j]) { ans++; } } } cout << ans; } return 0; }

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:70:13: warning: unused variable 'cnt' [-Wunused-variable]
   70 |         int cnt = 0;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...