Submission #489480

#	Time	Username	Problem	Language	Result	Execution time	Memory
489480		wiwiho	Virus Experiment (JOI19_virus)	C++14	0 / 100	73 ms	2892 KiB

virus

#include<bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n";\
}
#define eb emplace_back

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int m, r, c;
string wst;
vector<int> wind;
vector<vector<int>> g;
map<char, int> dirid;
vector<pii> dir = {mp(0, 1), mp(0, -1), mp(1, 0), mp(-1, 0)};
vector<int> len;

void init(){
    g.resize(r + 2, vector<int>(c + 2));
    wind.resize(m);
    len.resize(16);
    dirid['W'] = 0;
    dirid['E'] = 1;
    dirid['N'] = 2;
    dirid['S'] = 3;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> r >> c;
    cin >> wst;
    init();

    for(int i = 0; i < m; i++) wind[i] = dirid[wst[i]];

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++) cin >> g[i][j];
    }

    for(int i = 0; i < (1 << 4); i++){
        int now = 0;
        for(int j = 0; j < 3e5; j++){
            if(1 << wind[j % m] & i) now++;
            else now = 0;
            len[i] = max(len[i], now);
        }
        //cerr << "len " << bitset<4>(i) << " " << len[i] << "\n";
    }

    int ans = INT_MAX, cnt = 0;
    
    for(int i = 1; i <= r; i++){
        int now = 0;
        for(int j = 1; j <= c; j++){
            if(g[i][j] == 0){
                if(now > 0){
                    if(now < ans) ans = now, cnt = now;
                    else if(now == ans) cnt += now;
                }
                now = 0;
                continue;
            }
            if(g[i][j - 1] != 0 && len[1 << dirid['E']] >= g[i][j - 1] && len[1 << dirid['W']] >= g[i][j]){
                if(now > 0) now++;
            }
            else if(g[i][j - 1] != 0 && len[1 << dirid['E']] >= g[i][j - 1]){
                if(now > 0){
                    if(now < ans) ans = now, cnt = now;
                    else if(now == ans) cnt += now;
                }
                now = 0;
            }
            else{
                if(now > 0){
                    if(now < ans) ans = now, cnt = now;
                    else if(now == ans) cnt += now;
                }
                now = 1;
            }
            //cerr << "test " << i << " " << j << " " << now << "\n";
        }
        if(now > 0){
            if(now < ans) ans = now, cnt = now;
            else if(now == ans) cnt += now;
        }
    }

    cout << ans << "\n" << cnt << "\n";

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80