oj.uz

답안 #970247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970247 2024-04-26T09:27:03 Z efedmrlr 바이러스 (JOI19_virus) C++17
6 / 100
 2000 ms 6740 KB 
#include <bits/stdc++.h>

#define lli long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
array<int, 256> mpp;
array<array<int, 2>, 4> dir; 
array<int, 16> pos;

int m, r, c;
vector<int> day;
vector<vector<int> > u;
void calc_pos(int mask) {
    int ind = 0;
    pos[mask] = 0;
    int cur = 0;
    REP(i, N) {
        if((1 << day[ind]) & mask) {
            cur++;
        }
        else {
            pos[mask] = max(pos[mask], cur);
            cur = 0;
        }
        ind++; if(ind >= m) ind -= m;
    }
    pos[mask] = max(pos[mask], cur);
}
vector<vector<bool> > vis;



bool check(array<int, 2> nd) {
    if(u[nd[0]][nd[1]] == 0) return 0;
    int mask = 0;
    for(int i = 0; i < 4; i++) {
        array<int, 2> ch;
        REP(b, 2) {
            ch[b] = nd[b] + dir[i][b];
        }
        if(ch[0] < 0 || ch[0] >= r || ch[1] < 0 || ch[1] >= c) {
            continue;
        }
        if(vis[ch[0]][ch[1]]) mask += (1 << i);
    }

    if(pos[mask] >= u[nd[0]][nd[1]]) {
        return 1;
    }   
    return 0;
}

int dfs(array<int,2> cur) {
    vis[cur[0]][cur[1]] = 1;
    int ret = 1;
    for(int i = 0; i < 4; i++) {
        array<int, 2> ch;
        REP(b, 2) {
            ch[b] = cur[b] + dir[i][b];
            
        }
        if(ch[0] < 0 || ch[0] >= r || ch[1] < 0 || ch[1] >= c) {
            continue;
        }
        if(vis[ch[0]][ch[1]]) continue;
        if(check(ch)) {
            ret += dfs(ch);
        }
        
    }
    return ret;
}
vector<vector<int> > ans;
void solve() {
    cin >> m >> r >> c;
    day.resize(m);
    REP(i, m) {
        char cur;
        cin >> cur; 
        day[i] = mpp[cur];
    }   
    for(int i = 0; i < 16; i++) {
        calc_pos(i);
    }
    u.resize(r + 1, vector<int>(c + 1, 0));
    REP(i, r) {
        REP(j, c) {
            int x;
            cin >> x;
            u[i][j] = x;
        }
    }
    ans.assign(r + 1, vector<int>(c + 1, INF));
    REP(i, r) {
        REP(j, c) {
            if(u[i][j] == 0) continue;
            vis.assign(r + 1, vector<bool>(c + 1, 0));
            ans[i][j] = dfs({i, j});
        }
    }
    int mn = INF, cnt = 0;
    REP(i, r) {
        REP(j, c) {
            if(ans[i][j] < mn) {
                mn = ans[i][j]; cnt = 1;
            }
            else if(ans[i][j] == mn) {
                cnt++;
            }
        }
    }
    cout << mn << " " << cnt << "\n";

}

signed main() {
    mpp['N'] = 0;
    dir[0] = {-1, 0};
    mpp['S'] = 1;
    dir[1] = {1, 0};
    mpp['W'] = 2;
    dir[2] = {0, -1};
    mpp['E'] = 3;
    dir[3] = {0, 1};
    fastio();
    solve();
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 600 KB Output is correct
2 Execution timed out 2041 ms 6740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 8 ms 860 KB Output is correct
6 Correct 159 ms 1116 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 8 ms 860 KB Output is correct
9 Correct 78 ms 600 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 15 ms 496 KB Output is correct
12 Correct 226 ms 544 KB Output is correct
13 Correct 93 ms 964 KB Output is correct
14 Correct 99 ms 1116 KB Output is correct
15 Correct 97 ms 1112 KB Output is correct
16 Correct 137 ms 984 KB Output is correct
17 Correct 15 ms 600 KB Output is correct
18 Correct 17 ms 348 KB Output is correct
19 Correct 14 ms 860 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 600 KB Output is correct
2 Execution timed out 2041 ms 6740 KB Time limit exceeded
3 Halted 0 ms 0 KB -