Submission #154289

#	Time	Username	Problem	Language	Result	Execution time	Memory
154289		kungfulon	Nautilus (BOI19_nautilus)	C++14	100 / 100	200 ms	992 KiB

nautilus

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define repd(i,a,b) for(int i = a;i >= b;i--)
using namespace std;
const int N = 512;
int r,c,m;
bool a[N][N];
bitset<512> dp[N],temp[N],grid[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    ifstream cin ("nautilus.inp");
    cin >> r >> c >> m;
    rep(i,0,r-1)
    {
        rep(j,0,c-1)
        {
            char k;
            cin >> k;
            if(k == '.')
            {
                grid[i][c - j - 1] = 1;
                dp[i][c - j - 1] = 1;
            }

        }
    }
    rep(_,1,m)
    {
        char k;
        cin >> k;
        switch(k)
        {
        case 'N':
            {
                rep(i,1,r-1)
                    dp[i-1] = (dp[i] & grid[i-1]);
                dp[r-1].reset();
                break;
            }
        case 'E' :
            {
                rep(i,0,r-1)
                {
                    dp[i] >>= 1;
                    dp[i] &= grid[i];
                }

                break;
            }
        case 'S':
            {
                repd(i,r-1,1)
                    dp[i] = (dp[i-1] & grid[i]);
                dp[0].reset();
                break;
            }
        case 'W':
            {
                rep(i,0,r-1)
                {
                    dp[i] <<= 1;
                    dp[i] &= grid[i];
                }
                break;
            }
        default :
            {
                bitset<512> temp[N];
                rep(i,1,r-1) temp[i-1] |= dp[i];
                rep(i,0,r-1) temp[i] |= ((dp[i] >> 1) | (dp[i] << 1));
                repd(i,r-1,1) temp[i] |= dp[i-1];
                rep(i,0,r-1) temp[i] &= grid[i];
                rep(i,0,r-1) dp[i] = temp[i];
            }
        }
    }
    int ans = 0;
    rep(i,0,r-1)
        {
            rep(j,0,c-1) ans += dp[i][j];
        }
    cout << ans;
	return 0;
}

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