Submission #1084122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084122		_rain_	Nautilus (BOI19_nautilus)	C++14	100 / 100	242 ms	157616 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
#define fixbug false
#define ll long long

const int maxn = 500;
const int maxm = 5000;
char c[maxn+2][maxn+2];
string s;
int numrow , numcol , m;

namespace subtask1{
    bool check(){
        return numrow <= 100 && numcol <= 100 && m <= 500;
    }
    bool inside(int x , int y){
        return x > 0 && y > 0 && x <= numrow && y <= numcol && c[x][y] == '.';
    }
    const int maxN = 100;
    bool dp[maxN+1][maxN+1][maxN+1] = {};
    void main_code(){
        s = '#' + s;
        for (int i = 1; i <= numrow; ++i){
            for (int j = 1; j <= numcol; ++j)
                dp[i][j][0] = (c[i][j] == '.');
        }
        for (int t = 1; t <= m; ++t){
            vector<pair<int,int>> direct;
            if (s[t]=='?'){
                direct.push_back({0,1}); // E
                direct.push_back({0,-1}); // W
                direct.push_back({-1,0}); // N
                direct.push_back({1,0}); // S
            }
            else{
                if (s[t]=='E') direct.push_back({0,1});
                if (s[t]=='W') direct.push_back({0,-1});
                if (s[t]=='N') direct.push_back({-1,0});
                if (s[t]=='S') direct.push_back({1,0});
            }
            for (int i = 1; i <= numrow; ++i){
                for (int j = 1; j <= numcol; ++j){
                    if (dp[i][j][t-1]){
                        for (auto& x : direct){
                            int u = i + x.first , v = j + x.second;
                            if (inside(u,v)) dp[u][v][t] = true;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= numrow; ++i){
            for (int j = 1; j <= numcol; ++j) if (dp[i][j][m]) {
                ++ans;
                if (fixbug){
                    cout << i << ' ' << j << '\n';
                }
            }
        }
        cout << ans << '\n';
    }
}

namespace subtask2{
    bool check(){
        return true;
    }

    const int maxN = 500 , maxk = 5000;
    bitset<maxN+2> dp[maxN+2][maxk+2];
    bitset<maxN+2> oc[maxN+2];

    void main_code(){
        s = '#' + s;
        for (int i = 1; i <= numrow; ++i){
            for (int j = 1; j <= numcol ;++j){
                oc[i][j] = (c[i][j]=='.'?1:0);
            }
            dp[i][0] = oc[i];
        }
        int ans = 0;
        for (int t = 1; t <= m; ++t){
                for (int i = 1; i <= numrow; ++i){
                    if (s[t]=='?') dp[i][t] = (dp[i - 1][t - 1] | dp[i + 1][t - 1] | (dp[i][t - 1]<<1) | (dp[i][t-1]>>1))&oc[i];
                    if (s[t]=='E') dp[i][t] = (dp[i][t - 1] << 1) & oc[i];
                    if (s[t]=='W') dp[i][t] = (dp[i][t - 1] >> 1) & oc[i];
                    if (s[t]=='N') dp[i][t] = dp[i + 1][t - 1] & oc[i];
                    if (s[t]=='S') dp[i][t] = dp[i - 1][t - 1] & oc[i];
                }
        }
        if (fixbug){
            for (int t = 0; t <= 3; ++t){
                cout << "(DEBUG LAYER : " << t << ")\n";
                for (int i = 1; i <= numrow; ++i) {
                    for (int j = 1; j <= numcol; ++j) cout << dp[i][t][j] << ' ';
                    cout << '\n';
                }
            }
        }
        for (int i = 1; i <= numrow; ++i) ans += dp[i][m].count();
        cout << ans;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #define name "main"
   // freopen(name".inp","r",stdin);

    cin >> numrow >> numcol >> m;
    for (int i = 1; i <= numrow; ++i){
        for (int j = 1; j <= numcol; ++j){
            cin >> c[i][j];
        }
    }
    cin >> s;
    if (subtask1::check()) {
        subtask1::main_code();
        exit(0);
    }
    subtask2::main_code();
    exit(0);
}

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