Submission #377634

#	Time	Username	Problem	Language	Result	Execution time	Memory
377634		cpp219	Nautilus (BOI19_nautilus)	C++14	66 / 100	54 ms	10604 KiB

nautilus

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 100 + 9;
const ll inf = 1e16 + 7;
char a[N][N];
ll n,m,sz,dp[N][N][N];
string s;
char direct[4] = {'N','E','W','S'};
ll dx[4] = {-1,0,0,1};
ll dy[4] = {0,1,-1,0};

bool chk(ll x,ll y){
    return x > 0&&y > 0&&x <= n&&y <= m&&a[x][y] != '#';
}

ll f(ll x,ll y,ll cur){
    //cout<<x<<" "<<y<<" "<<cur<<"\n";
    if (cur > sz) return 1;
    if (dp[x][y][cur] != -1) return dp[x][y][cur];
    ll ans = 0;
    if (s[cur] != '?'){
        ll cx = x,cy = y;
        for (ll i = 0;i < 4;i++){
            if (s[cur] == direct[i]) cx += dx[i],cy += dy[i];
        }
        //if (cur == 6) cout<<cx<<" "<<cy<<" "<<f(cx,cy,cur + 1)<<"\n";
        if (chk(cx,cy)) ans = f(cx,cy,cur + 1);
    }
    else{
        for (ll i = 0;i < 4;i++){
            ll cx = x + dx[i],cy = y + dy[i];
            if (chk(cx,cy)){
                ans = max(ans,f(cx,cy,cur + 1));
                //if (cur == 5) cout<<cx<<" "<<cy<<" "<<f(cx,cy,cur + 1)<<"\n";
            }
        }
    }
    return dp[x][y][cur] = ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>m>>sz;
    for (ll i = 1;i <= n;i++)
        for (ll j = 1;j <= m;j++) cin>>a[i][j];
    cin>>s; s = " " + s; memset(dp,-1,sizeof(dp));
    for (ll i = 1;i <= sz;i++){
        if (s[i] == 'W') s[i] = 'E';
        else if (s[i] == 'E') s[i] = 'W';
        else if (s[i] == 'N') s[i] = 'S';
        else if (s[i] == 'S') s[i] = 'N';
    }
    reverse(s.begin(),s.end()); s = " " + s;
    ll ans = 0;
    for (ll i = 1;i <= n;i++)
        for (ll j = 1;j <= m;j++){
            //cout<<i<<" "<<j<<" "<<f(i,j,1)<<"\n";
            if (chk(i,j)) ans += f(i,j,1);
            //if (j > 2) return 0;
        }
    cout<<ans;
}

Compilation message (stderr)

nautilus.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
nautilus.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
nautilus.cpp: In function 'int main()':
nautilus.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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