Submission #1016610

#TimeUsernameProblemLanguageResultExecution timeMemory
1016610WhisperNautilus (BOI19_nautilus)C++17
66 / 100
14 ms9672 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, a, b) for (int i = (b); i >= (a); i --) #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPD(i, n) for (int i = (n) - 1; i >= 0; --i) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Phu Trong from Nguyen Tat Thanh High School for gifted student */ template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } int numRow, numCol, numSign; #define MAX 111 #define MAX_SIGN 111 char A[MAX][MAX]; char sign[MAX_SIGN]; int dp[MAX][MAX][MAX_SIGN]; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; pair<int, int> conv(char s){ if (s == 'N') return make_pair(-1, 0); if (s == 'S') return make_pair(1, 0); if (s == 'W') return make_pair(0, -1); return make_pair(0, 1); } bool inside(int x, int y){ return (x >= 1 && x <= numRow && y >= 1 && y <= numCol && A[x][y] != '#'); } void process(void){ cin >> numRow >> numCol >> numSign; FOR(i, 1, numRow) FOR(j, 1, numCol) cin >> A[i][j]; REP(i, numSign) cin >> sign[i]; FOR(x, 1, numRow) FOR(y, 1, numCol) if (A[x][y] != '#') dp[0][x][y] = 1; for (int i = 0; i < numSign; ++i){ FOR(x, 1, numRow) FOR(y, 1, numCol) if(A[x][y] != '#'){ if(sign[i] == '?'){ REP(dir, 4){ int nx = x + dx[dir], ny = y + dy[dir]; if (inside(nx, ny)){ dp[i + 1][nx][ny] |= dp[i][x][y]; } } } else{ pair<int, int> dir = conv(sign[i]); int nx = x + dir.first; int ny = y + dir.second; if (inside(nx, ny)) dp[i + 1][nx][ny] |= dp[i][x][y]; } } } int ans = 0; FOR(x, 1, numRow) FOR(y, 1, numCol) ans += dp[numSign][x][y]; cout << ans; } signed main(){ #define name "Whisper" cin.tie(nullptr) -> sync_with_stdio(false); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); process(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...