Submission #922486

#	Time	Username	Problem	Language	Result	Execution time	Memory
922486		raul2008487	Nautilus (BOI19_nautilus)	C++17	100 / 100	125 ms	1104 KiB

nautilus

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;
const int mod = 998244353;
const long long inf = 1000000000000000000;
const int sz = 505; /// mind the sz
bitset<sz> dp[2][sz], water[sz], x, y;
char a[sz][sz];
ll n, m;
void print(bitset<sz> A){
    for(ll i = 1; i<=m; i++){
        cout << A[i] << ' ';
    }
    cout << endl;
}
void solve(){
    ll i, j, k, c = 1;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j] == '.'){
                dp[0][i].set(j, 1);
                water[i].set(j, 1);
            }
        }
    }
    string s;
    cin >> s;
    s = "*" + s;
    for(i=1;i<=k;i++){
        for(j=1;j<=n;j++){
            dp[c][j] = x;
            if((s[i] == 'N' || s[i] == '?') && j < n){
                dp[c][j] |= dp[c ^ 1][j + 1];
            }
            if((s[i] == 'S' || s[i] == '?') && j > 1){
                dp[c][j] |= dp[c ^ 1][j - 1];
            }
            if(s[i] == 'W' || s[i] == '?'){
                dp[c][j] |= (dp[c ^ 1][j] >> 1);
            }
            if(s[i] == 'E' || s[i] == '?'){
                dp[c][j] |= (dp[c ^ 1][j] << 1);
            }
//            print(dp[c][j]);
//            print(water[j]);
            dp[c][j] &= water[j];
//            print(dp[c][j]);
        }
        c ^= 1;
//        break;
    }
    ll cnt = 0;
    for(i=1;i<=n;i++){
        //cout << i << " -> ";
        for(j=1;j<=m;j++){
            if(dp[k % 2][i][j]){
                //cout << j << ' ';
                cnt++;
            }
        }
        //cout << endl;
    }
    cout << cnt << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tst=1;
    //cin>>tst;             //MIND THIS
    while(tst--){
        solve();
    }
}
/*
1
6
4 1 6 3 10 7
*/

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