Submission #1305381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305381		veham	Nautilus (BOI19_nautilus)	C++20	66 / 100	1093 ms	832 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
typedef string str;
typedef vector<str> vs;

vector<bitset<500>> nesa(vector<bitset<500>> &G, vector<bitset<500>> &P, char dir, int R, int C){
    vector<bitset<500>> N(R);
    if(dir == 'N' || dir == '?'){
        for(int i = 1;i < R;i++){
            N[i-1] |= P[i];
        }
    }
    if(dir == 'S' || dir == '?'){
        for(int i = 0;i < R-1;i++){
            N[i+1] |= P[i];
        }
    }
    if(dir == 'W' || dir == '?'){
        for(int i = 0;i < R;i++){
            N[i] |= P[i]>>1;
        }
    }
    if(dir == 'E' || dir == '?'){
        for(int i = 0;i < R;i++){
            N[i] |= P[i]<<1;
        }
    }

    
    for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
            N[i] &= G[i];
        }
    }
    return N;
}

int main(){
    int R,C,M;
    cin >> R >> C >> M;
    vs G(R);
    for(int i = 0;i < R;i++) cin >> G[i];
    str D;
    cin >> D;
    vector<bitset<500>> G2(R),P2;
    for(int i = 0;i < R;i++) for(int j = 0;j < C;j++) G2[i][j] = G[i][j] == '.';
    P2 = G2;
    for(char dir : D) P2 = nesa(G2,P2,dir,R,C);
    int ans = 0;
    for(int i = 0;i < R;i++) ans += P2[i].count();
    cout << ans;
    return 0;
}

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