oj.uz

Submission #287540

# Submission time Handle Problem Language Result Execution time Memory
287540 2020-08-31T19:33:06 Z eagle30 Awesome Arrowland Adventure (eJOI19_adventure) C++14
50 / 100
 30 ms 15488 KB 
#include<bits/stdc++.h>
using namespace std;
char arr[1000][1000];
long long n, m, memo[3][501][1501], is[3][501][1501];
int dist(char a, char b){
    if(a=='N'){
        if(b=='N')
            return 0;
        else if(b=='E')
            return 1;
        else if(b=='S')
            return 2;
        else
            return 3;
    }
    else if(a=='E'){
        if(b=='N')
            return 3;
        else if(b=='E')
            return 0;
        else if(b=='S')
            return 1;
        else
            return 2;
    }
    else if(a=='S'){
        if(b=='N')
            return 2;
        else if(b=='E')
            return 3;
        else if(b=='S')
            return 0;
        else
            return 1;
    }
    else{
        if(b=='N')
            return 1;
        else if(b=='E')
            return 2;
        else if(b=='S')
            return 3;
        else
            return 0;
    }
}
long long recursive(long long hi1, long long hi2, long long yo){
    if(hi1<0 || hi1>=n || hi2<0 || hi2>=m)
        return 1000000000;
    if(hi1==n-1 && hi2==m-1)
        return 0;
    if(arr[hi1][hi2]=='X' || yo==0)
        return 1000000000;
    if(is[hi1][hi2][yo])
        return memo[hi1][hi2][yo];
    long long mini=2e9;
    char asdf=arr[hi1][hi2];
    mini=min(mini, recursive(hi1+1, hi2, yo-1)+dist(asdf, 'S'));
    mini=min(mini, recursive(hi1-1, hi2, yo-1)+dist(asdf, 'N'));
    mini=min(mini, recursive(hi1, hi2+1, yo-1)+dist(asdf, 'E'));
    mini=min(mini, recursive(hi1, hi2-1, yo-1)+dist(asdf, 'W'));
    is[hi1][hi2][yo]=true;
    return memo[hi1][hi2][yo]=mini;
}
int main(){
cin>>n>>m;
for(long long i=0; i<n; i++){
    for(long long j=0; j<m; j++){
        cin>>arr[i][j];
    }
}
if(recursive(0, 0, n*m)<1000000000)
    cout<<recursive(0, 0, n*m);
else
    cout<<-1;
return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 3200 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 2 ms 2176 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 2176 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 3200 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 2 ms 2176 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 2176 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 4 ms 3712 KB Output is correct
13 Correct 7 ms 6144 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 1920 KB Output is correct
16 Correct 4 ms 4352 KB Output is correct
17 Correct 5 ms 4480 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1664 KB Output is correct
20 Correct 6 ms 5888 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 1408 KB Output is correct
3 Correct 8 ms 6144 KB Output is correct
4 Correct 5 ms 4352 KB Output is correct
5 Correct 30 ms 15488 KB Output is correct
6 Correct 23 ms 12536 KB Output is correct
7 Correct 5 ms 4608 KB Output is correct
8 Correct 1 ms 1536 KB Output is correct
9 Correct 1 ms 1664 KB Output is correct
10 Correct 1 ms 1408 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 3200 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 2 ms 2176 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 2176 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 4 ms 3712 KB Output is correct
13 Correct 7 ms 6144 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 2 ms 1920 KB Output is correct
16 Correct 4 ms 4352 KB Output is correct
17 Correct 5 ms 4480 KB Output is correct
18 Correct 1 ms 1280 KB Output is correct
19 Correct 1 ms 1664 KB Output is correct
20 Correct 6 ms 5888 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 0 ms 256 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 1408 KB Output is correct
27 Correct 8 ms 6144 KB Output is correct
28 Correct 5 ms 4352 KB Output is correct
29 Correct 30 ms 15488 KB Output is correct
30 Correct 23 ms 12536 KB Output is correct
31 Correct 5 ms 4608 KB Output is correct
32 Correct 1 ms 1536 KB Output is correct
33 Correct 1 ms 1664 KB Output is correct
34 Correct 1 ms 1408 KB Output is correct
35 Runtime error 10 ms 4992 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -