oj.uz

Submission #123238

# Submission time Handle Problem Language Result Execution time Memory
123238 2019-06-30T15:15:10 Z miguel Nautilus (BOI19_nautilus) C++14
100 / 100
 194 ms 157408 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1000000007;
//#define int ll
int n, m, ss, ans;
set <pi> mp;
bitset<501> t[501];
bitset<501> dp[5002][501];
string s;

bool valid(int x, int y){
    if(x>0 && x<=n && y>0 && y<=m && t[x][y]) return 1;
    else return 0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>ss;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            if(c=='.') t[i][j]=1, dp[0][i][j]=1;
        }
    }
    cin>>s;
    for(int cur=0; cur<ss; cur++){
        for(int i=1; i<=n; i++){
            int x=i;
            char c=s[cur];
            if(c=='?'){
                dp[cur+1][x+1]|=(dp[cur][x]&t[x+1]);
                dp[cur+1][x]|=((dp[cur][x]<<1)&t[x]);
                dp[cur+1][x-1]|=(dp[cur][x]&t[x-1]);
                dp[cur+1][x]|=((dp[cur][x]>>1)&t[x]);
            }
            else if(c=='S'){
                dp[cur+1][x+1]|=(dp[cur][x]&t[x+1]);
            }
            else if(c=='E'){
                dp[cur+1][x]|=((dp[cur][x]<<1)&t[x]);
            }
            else if(c=='N'){
                dp[cur+1][x-1]|=(dp[cur][x]&t[x-1]);
            }
            else if(c=='W'){
                dp[cur+1][x]|=((dp[cur][x]>>1)&t[x]);
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(dp[ss][i][j]) ans++;
        }
    }
    cout<<ans;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1400 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1400 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 3 ms 1400 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 3 ms 1400 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 3 ms 1400 KB Output is correct
14 Correct 4 ms 1400 KB Output is correct
15 Correct 3 ms 1400 KB Output is correct
16 Correct 3 ms 1404 KB Output is correct
17 Correct 3 ms 1400 KB Output is correct
18 Correct 3 ms 1400 KB Output is correct
19 Correct 3 ms 1400 KB Output is correct
20 Correct 3 ms 1400 KB Output is correct
21 Correct 3 ms 1404 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1400 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 3 ms 1400 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 3 ms 1400 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 3 ms 1400 KB Output is correct
14 Correct 4 ms 1400 KB Output is correct
15 Correct 3 ms 1400 KB Output is correct
16 Correct 3 ms 1404 KB Output is correct
17 Correct 3 ms 1400 KB Output is correct
18 Correct 3 ms 1400 KB Output is correct
19 Correct 3 ms 1400 KB Output is correct
20 Correct 3 ms 1400 KB Output is correct
21 Correct 3 ms 1404 KB Output is correct
22 Correct 176 ms 157408 KB Output is correct
23 Correct 194 ms 157316 KB Output is correct
24 Correct 176 ms 157272 KB Output is correct
25 Correct 173 ms 157304 KB Output is correct
26 Correct 177 ms 157204 KB Output is correct
27 Correct 180 ms 157304 KB Output is correct
28 Correct 184 ms 157312 KB Output is correct
29 Correct 183 ms 157292 KB Output is correct
30 Correct 182 ms 157304 KB Output is correct
31 Correct 180 ms 157304 KB Output is correct
32 Correct 185 ms 157304 KB Output is correct
33 Correct 186 ms 157304 KB Output is correct
34 Correct 187 ms 157240 KB Output is correct
35 Correct 186 ms 157276 KB Output is correct
36 Correct 185 ms 157292 KB Output is correct