Submission #1124578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124578		gdragon	Nautilus (BOI19_nautilus)	C++20	66 / 100	39 ms	5180 KiB

nautilus

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 500 + 5;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
void add(int &x, int y) {x += y; if (x >= mod) x -= mod;}
void sub(int &x, int y) {x -= y; if (x < 0) x += mod;}
int mul(int x, int y) {return 1LL * x * y % mod;}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int direction(char c) {
    if (c == 'S') return 0;
    if (c == 'N') return 1;
    if (c == 'E') return 2;
    return 3;
}
// -----------------------------------------//
int n, m, len;
int a[N][N];
string s;
void read() {
    cin >> n >> m >> len;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char c; cin >> c;
            a[i][j] = (c == '.');
        }
    }
    cin >> s;
}
int f1[105][105][105];
bool used[105][105];
bool dfs(int x, int y, int i) {
    // if (x < 0) x += n;
    // if (x >= n) x -= n;
    // if (y < 0) y += m;
    // if (y >= m) y -= m;
    if (x >= n || y >= m || x < 0 || y < 0 || !a[x][y]) return 0;
    if (!a[x][y]) return 0;
    // if (i == 5) cerr << x << ' ' << y << endl;
    if (f1[x][y][i] != -1) return f1[x][y][i]; 
    // cerr << x << ' ' << y << ' ' << i << endl;
    if (i >= len) {
        f1[x][y][len] = 1;
        // used[x][y] = 1;
        return 1;
    }
    int &res = f1[x][y][i];
    res = 0;
    if (s[i] != '?') res = dfs(x + dx[direction(s[i])], y + dy[direction(s[i])], i + 1);
    else {
        for(int dir = 0; dir < 4; dir++) {
            if (dfs(x + dx[dir], y + dy[dir], i + 1)) {
                res = 1;
                // break;
            }
        }
    }
    // if (res) used[x][y] = 1;
    return res;
}
void sub1() {
    memset(f1, -1, sizeof(f1));
    int ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (a[i][j]) {
                dfs(i, j, 0);
                // if (dfs(i, j, 0)) cerr << i << ' ' << j << endl;
            }
        }
    }
    ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) if (f1[i][j][len] == 1) ++ans;
    }
    cout << ans;
}
void solve() {
    if (max({n, m, len}) <= 100) sub1();
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34