Submission #970247

#	Time	Username	Problem	Language	Result	Execution time	Memory
970247		efedmrlr	Virus Experiment (JOI19_virus)	C++17	6 / 100	2041 ms	6740 KiB

virus

#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
• Subtask 2: 6 / 6
• Subtask 3: 0 / 80