Submission #1103208

#TimeUsernameProblemLanguageResultExecution timeMemory
1103208vjudge1Nautilus (BOI19_nautilus)C++17
100 / 100
153 ms552 KiB
// Thanks to : TVA
// Strycks, L3, PAD, TVT, NGUYEN^2, Whisper
// My friends...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int, int>
#define plli pair<ll, int>
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define se second
#define For(i, a, b) for(int i = (a) ; i <= (b) ; ++i)
#define Ford(i, b, a) for(int i = (b) ; i >= (a) ; --i)
#define FILE freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout);
#define int long long

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using str = string;
using ld = long double;
using ull = unsigned long long;
using htype = unsigned long long;

template <class T> bool ckmin(T &a, const T &b) {return (a > b ? a = b, true : false); };
template <class T> bool ckmax(T &a, const T &b) {return (a < b ? a = b, true : false); };
template <class T> void compress(vector <T> &a) {sort(all(a)); a.resize(unique(all(a)) - a.begin()); };
template <class T> int getcom(vector<T> &a, T val) {return lower_bound(all(a), val) - a.begin() + 1; };

const ll mod = 1e9 + 7;                             /// MOD CHANGED

ll add(ll x, ll y){
    return (x + y) % mod;
}

ll sub(ll x, ll y){
    return ((x - y) % mod + mod) % mod;
}

ll mul(ll x, ll y){
    return (x * y) % mod;
}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

const int dx[] = {-1, 0, 0, 1};
const int dy[] = {0, -1, 1, 0};
const char MOVE[] = {'U', 'L', 'R', 'D'};

const ll INFll = 0x3f3f3f3f3f3f3f3f;
const int INFin = 0x3f3f3f3f;

const int maxn = 5e2 + 5;                           /// MAXN CHANGED

const int maxv = 1e6 + 5;                         /// MAXV CHANGED

bitset<maxn> b[2][maxn];
bitset<maxn> anti[maxn];

int r, c, w;

signed main(){
    fast
    #define name "Anya"
    // FILE
    cin >> r >> c >> w;
    For(i, 1, r){
        Ford(j, c, 1){
            char tmp; cin >> tmp;
            if(tmp == '.'){
                b[0][i][j] = 1;
                anti[i][j] = 1;
            }
        }
    }

    For(t, 1, w){
        bool state = (t % 2);

        char tp; cin >> tp;

        For(i, 1, r){
            if(tp == 'W') b[state][i] = ((b[!state][i] << 1) & anti[i]);
            else if(tp == 'E') b[state][i] = ((b[!state][i] >> 1) & anti[i]);
            else if(tp == 'N') b[state][i] = (b[!state][i + 1] & anti[i]);
            else if(tp == 'S') b[state][i] = (b[!state][i - 1] & anti[i]);
            else{
                b[state][i] = (((b[!state][i] << 1) | (b[!state][i] >> 1) | (b[!state][i + 1]) | (b[!state][i - 1])) & anti[i]);
            }
        }
    }

    ll ans = 0;

    For(i, 1, r){
        ans += b[w % 2][i].count();
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...