oj.uz

Submission #888817

# Submission time Handle Problem Language Result Execution time Memory
888817 2023-12-18T08:08:37 Z 12345678 Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 1116 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=505;
int r, c, m, dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, en[100], cnt;
char mp[nx][nx];
bool dp[2][nx][nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    en['N']=1; en['W']=0; en['E']=3; en['S']=2;
    cin>>r>>c>>m;
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cin>>mp[i][j], dp[0][i][j]=(mp[i][j]=='.');
    cin>>s;
    for (int i=1; i<=m; i++)
    {
        int cr=i%2, pv=1-cr;
        for (int j=1; j<=r; j++)
        {
            for (int k=1; k<=c; k++)
            {
                if (mp[j][k]!='#')
                {
                    if (s[i-1]=='?') for (int l=0; l<4; l++) dp[cr][j][k]|=dp[pv][j+dy[l]][k+dx[l]];
                    else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
                }
                if (i==m&&dp[cr][j][k]) cnt++;
            }
        }
        for (int j=1; j<=r; j++) for (int k=1; k<=c; k++) dp[pv][j][k]=0;
    }
    cout<<cnt;
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:31:60: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |                     else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
      |                                                            ^
nautilus.cpp:31:78: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |                     else dp[cr][j][k]=dp[pv][j+dy[en[s[i-1]]]][k+dx[en[s[i-1]]]];
      |                                                                              ^

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 4 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 5 ms 612 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 4 ms 600 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Execution timed out 1078 ms 1116 KB Time limit exceeded
23 Halted 0 ms 0 KB -