oj.uz

Submission #377634

# Submission time Handle Problem Language Result Execution time Memory
377634 2021-03-14T14:12:08 Z cpp219 Nautilus (BOI19_nautilus) C++14
66 / 100
 54 ms 10604 KB 
#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

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.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10604 KB Output is correct
2 Correct 9 ms 10476 KB Output is correct
3 Correct 7 ms 10476 KB Output is correct
4 Correct 6 ms 10476 KB Output is correct
5 Correct 6 ms 10476 KB Output is correct
6 Correct 6 ms 10476 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10604 KB Output is correct
2 Correct 9 ms 10476 KB Output is correct
3 Correct 7 ms 10476 KB Output is correct
4 Correct 6 ms 10476 KB Output is correct
5 Correct 6 ms 10476 KB Output is correct
6 Correct 6 ms 10476 KB Output is correct
7 Correct 37 ms 10476 KB Output is correct
8 Correct 12 ms 10476 KB Output is correct
9 Correct 7 ms 10476 KB Output is correct
10 Correct 6 ms 10476 KB Output is correct
11 Correct 6 ms 10476 KB Output is correct
12 Correct 50 ms 10476 KB Output is correct
13 Correct 42 ms 10476 KB Output is correct
14 Correct 28 ms 10476 KB Output is correct
15 Correct 7 ms 10476 KB Output is correct
16 Correct 7 ms 10476 KB Output is correct
17 Correct 54 ms 10476 KB Output is correct
18 Correct 47 ms 10476 KB Output is correct
19 Correct 14 ms 10496 KB Output is correct
20 Correct 9 ms 10604 KB Output is correct
21 Correct 6 ms 10476 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10604 KB Output is correct
2 Correct 9 ms 10476 KB Output is correct
3 Correct 7 ms 10476 KB Output is correct
4 Correct 6 ms 10476 KB Output is correct
5 Correct 6 ms 10476 KB Output is correct
6 Correct 6 ms 10476 KB Output is correct
7 Correct 37 ms 10476 KB Output is correct
8 Correct 12 ms 10476 KB Output is correct
9 Correct 7 ms 10476 KB Output is correct
10 Correct 6 ms 10476 KB Output is correct
11 Correct 6 ms 10476 KB Output is correct
12 Correct 50 ms 10476 KB Output is correct
13 Correct 42 ms 10476 KB Output is correct
14 Correct 28 ms 10476 KB Output is correct
15 Correct 7 ms 10476 KB Output is correct
16 Correct 7 ms 10476 KB Output is correct
17 Correct 54 ms 10476 KB Output is correct
18 Correct 47 ms 10476 KB Output is correct
19 Correct 14 ms 10496 KB Output is correct
20 Correct 9 ms 10604 KB Output is correct
21 Correct 6 ms 10476 KB Output is correct
22 Runtime error 3 ms 800 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -