oj.uz

Submission #482512

# Submission time Handle Problem Language Result Execution time Memory
482512 2021-10-25T08:32:09 Z Fidisk Nautilus (BOI19_nautilus) C++14
66 / 100
 1000 ms 972 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
typedef pair<long double,long long> pdl;

const ll base=361;
const ll mod=1e9;
const ll mod2=1e9;
const ld eps=1e-3;
const ld eps2=1e-7;
const ll maxn=1e6+9;
const ll maxsize=6e5+29;
const ld pi=acos(-1);
//const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};

const int dxkn[8]={1,1,2,2,-1,-1,-2,-2};
const int dykn[8]={2,-2,1,-1,2,-2,1,-1};
const int dxki[8]={1,1,1,0,0,-1,-1,-1};
const int dyki[8]={1,0,-1,1,-1,1,0,-1};

string s;
char ch;
int n,m,k,i,j,l,res;
bool f[3][509][509],a[509][509];

int main() {
    IO;
    cin>>n>>m>>k;
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            cin>>ch;
            if (ch=='.') {
                a[i][j]=true;
            }
            f[1][i][j]=a[i][j];
        }
    }
    cin>>s;
    s=" "+s;
    for (i=1;i<=k;i++) {
        for (j=1;j<=n;j++) {
            for (l=1;l<=m;l++) {
                f[(i+1)&1][j][l]=false;
            }
        }
        for (j=1;j<=n;j++) {
            for (l=1;l<=m;l++) {
                if (s[i]=='?') {
                    f[(i+1)&1][j-1][l]|=f[i&1][j][l]&a[j-1][l];
                    f[(i+1)&1][j+1][l]|=f[i&1][j][l]&a[j+1][l];
                    f[(i+1)&1][j][l-1]|=f[i&1][j][l]&a[j][l-1];
                    f[(i+1)&1][j][l+1]|=f[i&1][j][l]&a[j][l+1];
                }
                else if (s[i]=='S') {
                    f[(i+1)&1][j+1][l]|=f[i&1][j][l]&a[j+1][l];
                }
                else if (s[i]=='N') {
                    f[(i+1)&1][j-1][l]|=f[i&1][j][l]&a[j-1][l];
                }
                else if (s[i]=='E') {
                    f[(i+1)&1][j][l+1]|=f[i&1][j][l]&a[j][l+1];
                }
                else {
                    f[(i+1)&1][j][l-1]|=f[i&1][j][l]&a[j][l-1];
                }
            }
        }
        //for (j=1;j<=n;j++) {
        //    for (l=1;l<=m;l++) {
        //        cout<<f[i&1][j][l];
        //    }
         //   cout<<'\n';
        //}
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            res+=f[(k+1)&1][i][j];
            //cout<<f[(k+1)&1][i][j];
        }
        //cout<<'\n';
    }
    cout<<res<<'\n';
}

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 3 ms 440 KB Output is correct
12 Correct 3 ms 476 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 4 ms 460 KB Output is correct
15 Correct 4 ms 460 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 4 ms 460 KB Output is correct
18 Correct 4 ms 460 KB Output is correct
19 Correct 4 ms 472 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Execution timed out 1096 ms 972 KB Time limit exceeded
23 Halted 0 ms 0 KB -