Submission #926011

#TimeUsernameProblemLanguageResultExecution timeMemory
926011vjudge1Nautilus (BOI19_nautilus)C++17
100 / 100
96 ms536 KiB
//Bismillahir-Rahmanir-Rahim #include <bits/stdc++.h> #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops") #pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2") #define pb push_back #define pii pair <int, int> #define pll pair <long long, long long> #define pld pair <long double, long double> #define ll long long #define ld long double #define x first #define y second #define all(v) v.begin(),v.end() #define sz(s) (int)s.size() #define skip continue #define bpop(x) (ll)__builtin_popcountll(x) using namespace std; const int N = 5e2 + 7; const int M = 5e3 + 7; const int maxA = 2e6 + 7; const int inf = 1e9 + 7; const ll INF = 2e18 + 7; const int MOD = 1e9 + 7; const ld eps = 1e-9; pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define int long long int n, m, k; bool border(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= m; } int id[255]; bitset <N> fn[N], dp[N], dp2[N]; char s[M]; void shiftWE(char type) { for (int i = 1;i <= n;i++)dp2[i] = (dp2[i] | ((type == 'W' ? (dp[i] >> 1) : (dp[i] << 1)) & fn[i])); } void shiftNS(char type) { for (int i = 1;i <= n;i++)dp2[i] = (dp2[i] | ((type == 'N' ? dp[i + 1] : dp[i - 1]) & fn[i])); } void solve() { cin >> n >> m >> k; for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { char c; cin >> c; fn[i][j] = (c == '.' ? 1 : 0); } } for (int i = 1;i <= k;i++)cin >> s[i]; id['W'] = 0, id['N'] = 1, id['E'] = 2, id['S'] = 3; int ans = 0; for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (fn[i][j])dp[i][j] = 1; } }; for (int step = 1;step <= k;step++) { //cout << step << ":\n"; if (s[step] == '?')shiftWE('W'), shiftWE('E'), shiftNS('N'), shiftNS('S'); else { char type = s[step]; if (type == 'E' || type == 'W')shiftWE(type); else shiftNS(type); } for (int i = 1;i <= n;i++)dp[i] = dp2[i], dp2[i].reset(); } for (int i = 1;i <= n;i++)ans += dp[i].count(); cout << ans; } signed main() { //srand(time(NULL)); ios_base::sync_with_stdio(0); cout.tie(0); //freopen("tests.in", "r", stdin); //freopen("milkorder.out", "w", stdout); int test = 1; //cin >> test; for (int t = 1;t <= test;t++) { //cout << "Case " << t << ": "; solve(); } return 0; }

Compilation message (stderr)

nautilus.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:200000000")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...