Submission #723054

#	Time	Username	Problem	Language	Result	Execution time	Memory
723054		adrilen	Nautilus (BOI19_nautilus)	C++17	100 / 100	256 ms	157784 KiB

nautilus

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxm = 5e3 + 1, maxa = 5e2 + 2;

bitset <maxa> ma[maxm][maxa];

vector<pii> dir[] = { vector<pii>{pii( -1, 0 )}, vector<pii>{pii( 1, 0 )}, vector<pii>{pii( 0, -1 )},
                    vector<pii>{pii( 0, 1 )}, vector<pii>{pii( -1, 0 ), pii(1, 0), pii(0, -1), pii(0, 1)}};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int r, c, m;
    cin >> r >> c >> m;

    string s;
    for (int y = 1; y <= r; y++)
    {
        cin >> s;
        for (int x = 1; x <= c; x++)
        {
            if (s[x - 1] == '.') ma[0][x][y] = true;
        }
    }
    int output;

    cin >> s;
    int typ;
    for (int i = 1; i <= m; i++)
    {
        if (s[i - 1]=='W') typ = 0;
        else if (s[i - 1]=='E') typ = 1;
        else if (s[i - 1]=='N') typ = 2; 
        else if (s[i - 1] == 'S') typ = 3;
        else typ = 4;

        // cout << dir[typ][0].first << " " << dir[typ][0].second << " " << dir[typ].size() <<"\n";

        if (typ == 0 || typ == 4)
        {
            for (int x = 1; x < c; x++) 
            {
                ma[i][x] |= (ma[0][x] & ma[i - 1][x + 1]); 
            }
        }
        if (typ == 1 || typ == 4)
        {
            for (int x = 2; x <= c; x++)
            {
                ma[i][x] |= (ma[0][x] & ma[i - 1][x - 1]);
            }
        }
        if (typ == 2 || typ == 4)
        {
            for (int x = 1; x <= c; x++)
            {
                ma[i][x] |= (ma[0][x] & (ma[i - 1][x] >> 1));
            }
        }
        if (typ == 3 || typ == 4)
        {
            for (int x = 1; x<= c; x++)
            {
                ma[i][x] |= (ma[0][x] & (ma[i - 1][x] << 1));
            }
        }
    }
    // for (int i = 0; i <= m; i++)
    // {
    //     cout << i <<"\n";
    //     for (int y = 1; y <= r; y ++) 
    //     {
    //         for (int x = 1; x <= c; x++) cout << ma[i][x][y];
    //         cout << "\n";
    //     }
    //     cout <<"\n";
    // }

    output = 0;
    for (int x = 1; x <= c; x++)
    {
        output += ma[m][x].count();
    }
    cout << output << "\n";

    //cerr << clock() / static_cast<double>(CLOCKS_PER_SEC) << "\n";
}

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