oj.uz

Submission #1084091

# Submission time Handle Problem Language Result Execution time Memory
1084091 2024-09-05T07:06:17 Z _rain_ Nautilus (BOI19_nautilus) C++14
66 / 100
 13 ms 1528 KB 
#include<bits/stdc++.h>
using namespace std;
#define fixbug false
#define ll long long

const int maxn = 500;
const int maxm = 5000;
char c[maxn+2][maxn+2];
string s;
int numrow , numcol , m;

namespace subtask1{
    bool check(){
        return numrow <= 100 && numcol <= 100 && m <= 500;
    }
    bool inside(int x , int y){
        return x > 0 && y > 0 && x <= numrow && y <= numcol && c[x][y] == '.';
    }
    const int maxN = 100;
    bool dp[maxN+1][maxN+1][maxN+1] = {};
    void main_code(){
        s = '#' + s;
        for (int i = 1; i <= numrow; ++i){
            for (int j = 1; j <= numcol; ++j)
                dp[i][j][0] = (c[i][j] == '.');
        }
        for (int t = 1; t <= m; ++t){
            vector<pair<int,int>> direct;
            if (s[t]=='?'){
                direct.push_back({0,1}); // E
                direct.push_back({0,-1}); // W
                direct.push_back({-1,0}); // N
                direct.push_back({1,0}); // S
            }
            else{
                if (s[t]=='E') direct.push_back({0,1});
                if (s[t]=='W') direct.push_back({0,-1});
                if (s[t]=='N') direct.push_back({-1,0});
                if (s[t]=='S') direct.push_back({1,0});
            }
            for (int i = 1; i <= numrow; ++i){
                for (int j = 1; j <= numcol; ++j){
                    if (dp[i][j][t-1]){
                        for (auto& x : direct){
                            int u = i + x.first , v = j + x.second;
                            if (inside(u,v)) dp[u][v][t] = true;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= numrow; ++i){
            for (int j = 1; j <= numcol; ++j) if (dp[i][j][m]) {
                ++ans;
                if (fixbug){
                    cout << i << ' ' << j << '\n';
                }
            }
        }
        cout << ans << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #define name ""
    //freopen(name".inp","r",stdin);

    cin >> numrow >> numcol >> m;
    for (int i = 1; i <= numrow; ++i){
        for (int j = 1; j <= numcol; ++j){
            cin >> c[i][j];
            if (fixbug){
                cout << c[i][j] << " \n"[j==numcol];
            }
        }
    }
    cin >> s;
    if (subtask1::check()) {
        subtask1::main_code();
        exit(0);
    }
}

Subtask #1
29.0 / 29.0

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

Subtask #2
37.0 / 37.0

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

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 3 ms 1372 KB Output is correct
4 Correct 3 ms 1372 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 6 ms 1372 KB Output is correct
8 Correct 5 ms 1524 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 3 ms 1372 KB Output is correct
11 Correct 3 ms 1368 KB Output is correct
12 Correct 9 ms 1368 KB Output is correct
13 Correct 11 ms 1372 KB Output is correct
14 Correct 10 ms 1528 KB Output is correct
15 Correct 3 ms 1372 KB Output is correct
16 Correct 3 ms 1372 KB Output is correct
17 Correct 12 ms 1372 KB Output is correct
18 Correct 13 ms 1372 KB Output is correct
19 Correct 8 ms 1372 KB Output is correct
20 Correct 3 ms 1372 KB Output is correct
21 Correct 3 ms 1372 KB Output is correct
22 Incorrect 3 ms 860 KB Output isn't correct
23 Halted 0 ms 0 KB -