| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1116561 |
2024-11-21T19:56:00 Z |
xnqs |
Nautilus (BOI19_nautilus) |
C++17 |
|
64 ms |
1116 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt,lzcnt")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <bitset>
int x, y, p;
char arr[505][505];
char moves[5005];
std::bitset<505> dp[2][505];
std::bitset<505> row[505];
void solve_dp() {
for (int i = 0; i < x; i++) {
dp[0][i] = row[i];
}
for (int pos = 1; pos <= p; pos++) {
int curr = pos&1;
int last = (pos-1)&1;
for (int i = 0; i < x; i++) {
dp[curr][i].reset();
switch (moves[pos-1]) {
case 'N':
dp[curr][i] = dp[last][i+1] & row[i];
break;
case 'S':
dp[curr][i] = dp[last][i-1] & row[i];
break;
case 'E':
dp[curr][i] = (dp[last][i]<<1) & row[i];
break;
case 'W':
dp[curr][i] = (dp[last][i]>>1) & row[i];
break;
default:
dp[curr][i] |= dp[last][i+1];
dp[curr][i] |= dp[last][i-1];
dp[curr][i] |= (dp[last][i]<<1);
dp[curr][i] |= (dp[last][i]>>1);
dp[curr][i] &= row[i];
break;
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> y >> p;
for (int i = 0; i < x; i++) {
std::cin >> arr[i];
for (int j = 0; j < y; j++) {
row[i][j] = ((arr[i][j]=='.') ? 1 : 0);
}
}
std::cin >> moves;
solve_dp();
int ret = 0;
for (int i = 0; i < x; i++) {
ret += dp[p&1][i].count();
}
std::cout << ret << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
2 ms |
336 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
2 ms |
336 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
2 ms |
336 KB |
Output is correct |
| 10 |
Correct |
2 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
2 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
336 KB |
Output is correct |
| 18 |
Correct |
1 ms |
336 KB |
Output is correct |
| 19 |
Correct |
2 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
2 ms |
336 KB |
Output is correct |
| 6 |
Correct |
2 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
2 ms |
336 KB |
Output is correct |
| 10 |
Correct |
2 ms |
336 KB |
Output is correct |
| 11 |
Correct |
1 ms |
336 KB |
Output is correct |
| 12 |
Correct |
1 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
336 KB |
Output is correct |
| 14 |
Correct |
1 ms |
336 KB |
Output is correct |
| 15 |
Correct |
2 ms |
336 KB |
Output is correct |
| 16 |
Correct |
1 ms |
336 KB |
Output is correct |
| 17 |
Correct |
1 ms |
336 KB |
Output is correct |
| 18 |
Correct |
1 ms |
336 KB |
Output is correct |
| 19 |
Correct |
2 ms |
336 KB |
Output is correct |
| 20 |
Correct |
1 ms |
336 KB |
Output is correct |
| 21 |
Correct |
1 ms |
336 KB |
Output is correct |
| 22 |
Correct |
24 ms |
592 KB |
Output is correct |
| 23 |
Correct |
26 ms |
1016 KB |
Output is correct |
| 24 |
Correct |
24 ms |
1020 KB |
Output is correct |
| 25 |
Correct |
24 ms |
848 KB |
Output is correct |
| 26 |
Correct |
28 ms |
1116 KB |
Output is correct |
| 27 |
Correct |
34 ms |
1016 KB |
Output is correct |
| 28 |
Correct |
34 ms |
848 KB |
Output is correct |
| 29 |
Correct |
35 ms |
848 KB |
Output is correct |
| 30 |
Correct |
34 ms |
848 KB |
Output is correct |
| 31 |
Correct |
33 ms |
848 KB |
Output is correct |
| 32 |
Correct |
51 ms |
1056 KB |
Output is correct |
| 33 |
Correct |
40 ms |
848 KB |
Output is correct |
| 34 |
Correct |
64 ms |
848 KB |
Output is correct |
| 35 |
Correct |
44 ms |
848 KB |
Output is correct |
| 36 |
Correct |
40 ms |
848 KB |
Output is correct |
