| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 242963 |
2020-06-30T03:07:37 Z |
socho |
Nautilus (BOI19_nautilus) |
C++14 |
|
234 ms |
32540 KB |
#include "bits/stdc++.h"
using namespace std;
void fast() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
}
void ran() {
srand(chrono::steady_clock::now().time_since_epoch().count());
}
long long get_rand() {
long long a = rand();
long long b = rand();
return a * (RAND_MAX + 1ll) + b;
}
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000;
// int MOD = 998244353;
const int MXN = 505, MXT = 1005;
bitset<MXN> sea[MXN], inr[MXN];
int n, m, k;
bitset<MXN> dp[MXN][MXT];
signed main() {
ran(); fast();
for (int i=0; i<MXN; i++) {
for (int j=0; j<MXN; j++) {
sea[i][j] = 0;
inr[i][j] = 0;
dp[i][j] = 0;
}
}
cin >> n >> m >> k;
for (int i=0; i<n; i++) {
string s;
cin >> s;
for (int j=0; j<m; j++) {
if (s[j] == '.') sea[i][j] = dp[i][0][j] = true;
inr[i][j] = true;
}
}
string s;
cin >> s;
int f = 0;
for (auto x: s) {
if (x == 'E') {
for (int i=0; i<n; i++) {
dp[i][f+1] = (dp[i][f] << 1) & sea[i];
}
}
else if (x == 'W') {
for (int i=0; i<n; i++) {
dp[i][f+1] = (dp[i][f] >> 1) & sea[i];
}
}
else if (x == 'N') {
for (int i=0; i<n; i++) {
if (i == n-1) {
// empty line
dp[i][f+1] = sea[MXN-1];
}
else {
// normal
dp[i][f+1] = dp[i+1][f] & sea[i];
}
}
}
else if (x == 'S') {
for (int i=0; i<n; i++) {
if (i == 0) {
// empty line
dp[i][f+1] = sea[MXN-1];
}
else {
// normal
dp[i][f+1] = dp[i-1][f] & sea[i];
}
}
}
else {
// any
for (int i=0; i<n; i++) {
if (i == 0) {
dp[i][f+1] = (dp[i+1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
}
else if (i == n-1) {
dp[i][f+1] = (dp[i-1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
}
else {
dp[i][f+1] = (dp[i+1][f] | dp[i-1][f] | (dp[i][f] << 1) | (dp[i][f] >> 1)) & sea[i];
}
}
}
f++;
}
int x = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (dp[i][f][j]) x++;
}
}
cout << x << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
18432 KB |
Output is correct |
| 2 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 4 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18432 KB |
Output is correct |
| 6 |
Correct |
15 ms |
18432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
18432 KB |
Output is correct |
| 2 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 4 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18432 KB |
Output is correct |
| 6 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 7 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 8 |
Correct |
13 ms |
18432 KB |
Output is correct |
| 9 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 10 |
Correct |
14 ms |
18304 KB |
Output is correct |
| 11 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 12 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 13 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 14 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 15 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 16 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 17 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 18 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 19 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 20 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 21 |
Correct |
15 ms |
18432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
18432 KB |
Output is correct |
| 2 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 3 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 4 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 5 |
Correct |
13 ms |
18432 KB |
Output is correct |
| 6 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 7 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 8 |
Correct |
13 ms |
18432 KB |
Output is correct |
| 9 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 10 |
Correct |
14 ms |
18304 KB |
Output is correct |
| 11 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 12 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 13 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 14 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 15 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 16 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 17 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 18 |
Correct |
14 ms |
18432 KB |
Output is correct |
| 19 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 20 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 21 |
Correct |
15 ms |
18432 KB |
Output is correct |
| 22 |
Correct |
118 ms |
32504 KB |
Output is correct |
| 23 |
Correct |
120 ms |
32504 KB |
Output is correct |
| 24 |
Correct |
115 ms |
32380 KB |
Output is correct |
| 25 |
Correct |
115 ms |
32504 KB |
Output is correct |
| 26 |
Correct |
116 ms |
32376 KB |
Output is correct |
| 27 |
Correct |
177 ms |
32376 KB |
Output is correct |
| 28 |
Correct |
184 ms |
32520 KB |
Output is correct |
| 29 |
Correct |
182 ms |
32424 KB |
Output is correct |
| 30 |
Correct |
182 ms |
32376 KB |
Output is correct |
| 31 |
Correct |
179 ms |
32376 KB |
Output is correct |
| 32 |
Correct |
234 ms |
32348 KB |
Output is correct |
| 33 |
Correct |
233 ms |
32504 KB |
Output is correct |
| 34 |
Correct |
234 ms |
32504 KB |
Output is correct |
| 35 |
Correct |
231 ms |
32376 KB |
Output is correct |
| 36 |
Correct |
232 ms |
32540 KB |
Output is correct |
