oj.uz

Submission #154944

# Submission time Handle Problem Language Result Execution time Memory
154944 2019-09-25T15:36:08 Z GoldNextYear Nautilus (BOI19_nautilus) C++14
66 / 100
 52 ms 11064 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n,m,k;
string path;
string s[109];
int dp[109][109][109];
int done[109][109];
int bt(int id,int x,int y){
        if(s[x][y]=='#')return 0;
        int &ret=dp[id][x][y];
        if(ret!=-1)return 0;
        if(id==k){
                if(done[x][y]==0){
                        done[x][y]=1;
                        return 1;
                }
                else return 0;
        }
        ret=0;
        if(path[id]=='N' && x-1>=0)ret+=bt(id+1,x-1,y);
        if(path[id]=='S' && x+1<n)ret+=bt(id+1,x+1,y);
        if(path[id]=='E' && y+1<m)ret+=bt(id+1,x,y+1);
        if(path[id]=='W' && y-1>=0)ret+=bt(id+1,x,y-1);
        if(path[id]=='?'){
                if(x-1>=0)ret+=bt(id+1,x-1,y);
                if(x+1<n)ret+=bt(id+1,x+1,y);
                if(y+1<m)ret+=bt(id+1,x,y+1);
                if(y-1>=0)ret+=bt(id+1,x,y-1);
        }
        return ret;
}
int main(){
        mem(dp,-1);
        cin>>n>>m>>k;
        for(int i=0;i<n;i++)cin>>s[i];
        cin>>path;
        int sum=0;
        for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                        if(s[i][j]!='#')sum+=bt(0,i,j);
                }
        }
        cout<<sum<<endl;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5624 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5624 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct
7 Correct 36 ms 5496 KB Output is correct
8 Correct 14 ms 5468 KB Output is correct
9 Correct 9 ms 5368 KB Output is correct
10 Correct 8 ms 5468 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 45 ms 5488 KB Output is correct
13 Correct 41 ms 5468 KB Output is correct
14 Correct 32 ms 5496 KB Output is correct
15 Correct 9 ms 5496 KB Output is correct
16 Correct 8 ms 5496 KB Output is correct
17 Correct 52 ms 5548 KB Output is correct
18 Correct 47 ms 5496 KB Output is correct
19 Correct 24 ms 5496 KB Output is correct
20 Correct 14 ms 5500 KB Output is correct
21 Correct 7 ms 5368 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5624 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 8 ms 5368 KB Output is correct
4 Correct 8 ms 5368 KB Output is correct
5 Correct 7 ms 5496 KB Output is correct
6 Correct 8 ms 5368 KB Output is correct
7 Correct 36 ms 5496 KB Output is correct
8 Correct 14 ms 5468 KB Output is correct
9 Correct 9 ms 5368 KB Output is correct
10 Correct 8 ms 5468 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 45 ms 5488 KB Output is correct
13 Correct 41 ms 5468 KB Output is correct
14 Correct 32 ms 5496 KB Output is correct
15 Correct 9 ms 5496 KB Output is correct
16 Correct 8 ms 5496 KB Output is correct
17 Correct 52 ms 5548 KB Output is correct
18 Correct 47 ms 5496 KB Output is correct
19 Correct 24 ms 5496 KB Output is correct
20 Correct 14 ms 5500 KB Output is correct
21 Correct 7 ms 5368 KB Output is correct
22 Runtime error 18 ms 11064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -