oj.uz

Submission #496446

# Submission time Handle Problem Language Result Execution time Memory
496446 2021-12-21T08:15:47 Z Ziel Nautilus (BOI19_nautilus) C++17
100 / 100
 181 ms 160588 KB 
/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");

#define int ll

bitset<510> dp[5010][510];

void solve() {
    int r, c, m;
    cin >> r >> c >> m;
    vector<vector<char>> a(r + 1, vector<char>(c + 1));
    for (int i = 1; i <= r; i++) {
    	for (int j = 1; j <= c; j++) {
    		cin >> a[i][j];
    	}
    }
    string s;
    cin >> s;
    auto in_frame = [r, c](int x, int y) -> bool {
    	return x >= 1 && x <= r && y >= 1 && y <= c;
    };

    for (int i = 1; i <= r; i++) {
    	for (int j = 1; j <= c; j++) {
    		if (a[i][j] == '.')
	    		dp[0][i][j] = 1;
    	}
    }

    /*for (int k = 0; k <= m; k++) {
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				cout << dp[k][i][j] << ' ';
			}
			cout << '\n';
		}
		cout << "\n\n";
	}
	cout << "--------------------------------------------------------------------------\n";
	*/
    for (int k = 1; k <= m; k++) {
    	for (int i = 1; i <= r; i++) {
    		if (s[k - 1] == '?') {
    			dp[k][i] |= (dp[k - 1][i - 1] & dp[0][i]);
    			dp[k][i] |= (dp[k - 1][i + 1] & dp[0][i]);
    			dp[k][i] |= ((dp[k - 1][i] << 1) & dp[0][i]);
    			dp[k][i] |= ((dp[k - 1][i] >> 1) & dp[0][i]);
    		} else if (s[k - 1] == 'N') {
    			dp[k][i] |= (dp[k - 1][i + 1] & dp[0][i]);
    		} else if (s[k - 1] == 'S') {
    			dp[k][i] |= (dp[k - 1][i - 1] & dp[0][i]);
    		} else if (s[k - 1] == 'E') {
    			dp[k][i] |= ((dp[k - 1][i] << 1) & dp[0][i]);
    		} else {
    			dp[k][i] |= ((dp[k - 1][i] >> 1) & dp[0][i]);
    		}
    	}
    }

/*
	for (int k = 0; k <= m; k++) {
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (k == 0) {
					if (a[i][j] == '.')
						dp[i][j][k] = true;
				} else {
					if (a[i][j] == '#') {
						dp[i][j][k] = false;
						continue;
					}
					if (s[k - 1] == '?') {
						if (in_frame(i - 1, j))
							dp[i][j][k] |= dp[i - 1][j][k - 1];
						if (in_frame(i + 1, j))
							dp[i][j][k] |= dp[i + 1][j][k - 1];
						if (in_frame(i, j - 1))
							dp[i][j][k] |= dp[i][j - 1][k - 1];
						if (in_frame(i, j + 1))
							dp[i][j][k] |= dp[i][j + 1][k - 1];
					} else if (s[k - 1] == 'N' && in_frame(i + 1, j)) {
						dp[i][j][k] |= dp[i + 1][j][k - 1];
					} else if (s[k - 1] == 'S' && in_frame(i - 1, j)) {
						dp[i][j][k] |= dp[i - 1][j][k - 1];
					} else if (s[k - 1] == 'E' && in_frame(i, j - 1)) {
						dp[i][j][k] |= dp[i][j - 1][k - 1];
					} else if (s[k - 1] == 'W' && in_frame(i, j + 1)) {
						dp[i][j][k] |= dp[i][j + 1][k - 1];
					}
				}
			}
		}
	}        */
/*
	for (int k = 0; k <= m; k++) {
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				cout << dp[k][i][j] << ' ';
			}
			cout << '\n';
		}
		cout << "\n\n";
	}*/

	int ans = 0;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			ans += dp[m][i][j];
		}
	}
	cout << ans;
}

signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> tt;
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

nautilus.cpp: In function 'void solve()':
nautilus.cpp:29:10: warning: variable 'in_frame' set but not used [-Wunused-but-set-variable]
   29 |     auto in_frame = [r, c](int x, int y) -> bool {
      |          ^~~~~~~~
nautilus.cpp: In function 'void setIO(const string&)':
nautilus.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 1 ms 1356 KB Output is correct
13 Correct 2 ms 1356 KB Output is correct
14 Correct 1 ms 1356 KB Output is correct
15 Correct 1 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 2 ms 1356 KB Output is correct
18 Correct 2 ms 1356 KB Output is correct
19 Correct 2 ms 1356 KB Output is correct
20 Correct 1 ms 1228 KB Output is correct
21 Correct 2 ms 1356 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 2 ms 1356 KB Output is correct
12 Correct 1 ms 1356 KB Output is correct
13 Correct 2 ms 1356 KB Output is correct
14 Correct 1 ms 1356 KB Output is correct
15 Correct 1 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 2 ms 1356 KB Output is correct
18 Correct 2 ms 1356 KB Output is correct
19 Correct 2 ms 1356 KB Output is correct
20 Correct 1 ms 1228 KB Output is correct
21 Correct 2 ms 1356 KB Output is correct
22 Correct 113 ms 160184 KB Output is correct
23 Correct 120 ms 160472 KB Output is correct
24 Correct 127 ms 160584 KB Output is correct
25 Correct 116 ms 160444 KB Output is correct
26 Correct 113 ms 160516 KB Output is correct
27 Correct 150 ms 160432 KB Output is correct
28 Correct 145 ms 160464 KB Output is correct
29 Correct 147 ms 160460 KB Output is correct
30 Correct 147 ms 160456 KB Output is correct
31 Correct 145 ms 160456 KB Output is correct
32 Correct 178 ms 160516 KB Output is correct
33 Correct 172 ms 160504 KB Output is correct
34 Correct 176 ms 160440 KB Output is correct
35 Correct 178 ms 160492 KB Output is correct
36 Correct 181 ms 160588 KB Output is correct