Submission #1106777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106777		minhvule	Nautilus (BOI19_nautilus)	C++17	100 / 100	144 ms	158888 KiB

nautilus

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define freo(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
#define FOR(i, a, b) for(int i=(a),_b = (b); i<=_b; i++)
#define FORD(i, a, b) for(int i=(a),_b = (b); i>=_b; i--)
#define bit(x, i) ((x >> i) & 1)
#define oo 1e18
#define pii pair<int, int>
#define debug cout<<"VUDEPTRAI\n";
using namespace std;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 5e3 + 5;
int r, c, m, ans = 0;
char a[505][505];
string s;
bitset<505> dp[N][505], mask[505];
void solve(){
    cin>>r>>c>>m;
    FOR(i, 1, r)
        FOR(j, 1, c)
            cin>>a[i][j];
    cin>>s;
    s = ' ' + s;
    FOR(i, 1, r)
        FOR(j, 1, c)
            if(a[i][j] == '.') dp[0][i].set(j), mask[i].set(j);
    FOR(i, 1, m)
        FOR(row, 1, r){
            if(s[i] == '?' || s[i] == 'N') dp[i][row] |= dp[i - 1][row + 1];
            if(s[i] == '?' || s[i] == 'S') dp[i][row] |= dp[i - 1][row - 1];
            if(s[i] == '?' || s[i] == 'E') dp[i][row] |= (dp[i - 1][row] << 1);
            if(s[i] == '?' || s[i] == 'W') dp[i][row] |= (dp[i - 1][row] >> 1);
            dp[i][row] &= mask[row];
        }
    FOR(row, 1, r) ans += dp[m][row].count();
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    // freo("");
    int nTest = 1;
    // cin>>nTest;
    while(nTest --) solve();
    // cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}
/*
 


*/

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 34 / 34