oj.uz

Submission #1029287

# Submission time Handle Problem Language Result Execution time Memory
1029287 2024-07-20T15:21:03 Z Marco_Escandon Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 198848 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll dx[]={1, 0, -1, 0};
ll dy[]={0, 1, 0, -1};
char cad[505][505];
string s;
pair<ll,ll> d(char car)
{
    if(car=='N')
        return {1,0};
    if(car=='S')
        return {-1,0};
    if(car=='W')
        return {0,1};
    if(car=='E')
        return {0,-1};
}
vector<vector<map<ll,ll>>> mapa;
ll sol(ll px, ll py, ll p)
{
    if(cad[px][py]=='#') return -1;
    if(p==s.size()) return 1;
    if(mapa[px][py][p]!=0) return mapa[px][py][p];
    if(s[p]!='?')
    {
        pair<ll,ll> car=d(s[p]);
        return mapa[px][py][p]=sol(car.first+px,py+car.second,p+1);
    }
    ll bs=-1;
    for(int i=0; i<4; i++){
        bs=max(bs,sol(px+dx[i],py+dy[i],p+1));
    }
    return mapa[px][py][p] = bs;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n,m,k;
    cin>>n>>m>>k;
    for(int i=0; i<=n+2; i++)
        for(int j=0;j<=m+2; j++)
            cad[i][j]='#';

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>cad[i][j];
    mapa.assign(505,vector<map<ll,ll>>(505));
    cin>>s;
    reverse(s.begin(),s.end());
    ll cont=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cont+=max(sol(i,j,0),0);
        }
    }
    cout<<cont;
    return 0;
}

Compilation message

nautilus.cpp: In function 'll sol(ll, ll, ll)':
nautilus.cpp:23:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(p==s.size()) return 1;
      |        ~^~~~~~~~~~
nautilus.cpp: In function 'std::pair<int, int> d(char)':
nautilus.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 54364 KB Output is correct
2 Correct 14 ms 16752 KB Output is correct
3 Correct 9 ms 14172 KB Output is correct
4 Correct 7 ms 12624 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 54364 KB Output is correct
2 Correct 14 ms 16752 KB Output is correct
3 Correct 9 ms 14172 KB Output is correct
4 Correct 7 ms 12624 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 173 ms 58368 KB Output is correct
8 Correct 29 ms 19284 KB Output is correct
9 Correct 9 ms 13404 KB Output is correct
10 Correct 7 ms 12636 KB Output is correct
11 Correct 8 ms 12636 KB Output is correct
12 Correct 296 ms 59420 KB Output is correct
13 Correct 212 ms 46928 KB Output is correct
14 Correct 98 ms 33872 KB Output is correct
15 Correct 9 ms 13656 KB Output is correct
16 Correct 6 ms 12636 KB Output is correct
17 Correct 288 ms 59236 KB Output is correct
18 Correct 220 ms 50260 KB Output is correct
19 Correct 64 ms 28976 KB Output is correct
20 Correct 19 ms 18268 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 54364 KB Output is correct
2 Correct 14 ms 16752 KB Output is correct
3 Correct 9 ms 14172 KB Output is correct
4 Correct 7 ms 12624 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 5 ms 12380 KB Output is correct
7 Correct 173 ms 58368 KB Output is correct
8 Correct 29 ms 19284 KB Output is correct
9 Correct 9 ms 13404 KB Output is correct
10 Correct 7 ms 12636 KB Output is correct
11 Correct 8 ms 12636 KB Output is correct
12 Correct 296 ms 59420 KB Output is correct
13 Correct 212 ms 46928 KB Output is correct
14 Correct 98 ms 33872 KB Output is correct
15 Correct 9 ms 13656 KB Output is correct
16 Correct 6 ms 12636 KB Output is correct
17 Correct 288 ms 59236 KB Output is correct
18 Correct 220 ms 50260 KB Output is correct
19 Correct 64 ms 28976 KB Output is correct
20 Correct 19 ms 18268 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct
22 Execution timed out 1064 ms 198848 KB Time limit exceeded
23 Halted 0 ms 0 KB -