Submission #365689

#	Time	Username	Problem	Language	Result	Execution time	Memory
365689		Yomapeed	Nautilus (BOI19_nautilus)	C++17	100 / 100	273 ms	1260 KiB

nautilus

#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 5e2;
bitset<N> dp[N], nxt[N], grid[N];
string s, t[N];
int r, c, m;
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        
        cin >> r >> c >> m;
        for(i = 0; i < r; i++){
            cin >> t[i];
            dp[i] = 0, grid[i] = 0;
            for(j = 0; j < c; j++){
                grid[i][j] = (t[i][j]  == '.');
            }
            dp[i] = grid[i];
        }
        cin >> s;
        for(auto u : s){
            for(i = 0; i < r; i++){
                nxt[i] = 0;
            }
            if(u == 'E' || u == '?'){
                for(i = 0; i < r; i++){
                    nxt[i] |= (dp[i] << 1);
                }
            }
            if(u == 'W' || u == '?'){
                for(i = 0; i < r; i++){
                    nxt[i] |= (dp[i] >> 1);
                }
            }
            if(u == 'S' || u == '?'){
                for(i = 1; i < r; i++){
                    nxt[i] |= (dp[i - 1]);
                }
            }
            if(u == 'N' || u == '?'){
                for(i = 0; i < r - 1; i++){
                    nxt[i] |= (dp[i + 1]);
                }
            }
            for(i = 0; i < r; i++){
                dp[i] = (nxt[i] & grid[i]);
            }
        }
        int ans = 0;
        for(i = 0; i < r; i++){
            ans += dp[i].count();
        }
        cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

nautilus.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
nautilus.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

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