Submission #1084091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084091		_rain_	Nautilus (BOI19_nautilus)	C++14	66 / 100	13 ms	1528 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';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #define name ""
    //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];
            if (fixbug){
                cout << c[i][j] << " \n"[j==numcol];
            }
        }
    }
    cin >> s;
    if (subtask1::check()) {
        subtask1::main_code();
        exit(0);
    }
}

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