Submission #489755

#	Time	Username	Problem	Language	Result	Execution time	Memory
489755		AA_Surely	Virus Experiment (JOI19_virus)	C++14	14 / 100	52 ms	10820 KiB

virus

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 800 + 7;
const int ALPHA = 40;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int m, r, c, le, lw;
int ns[MAXN][MAXN], lps[MAXN][MAXN], rps[MAXN][MAXN];
bool effect[MAXN][MAXN][2];
string per;

#define EAST 1
#define WEST 0

int main() {
    IOS;
    cin >> m >> r >> c;
    cin >> per;
    F0R(i, r) F0R(j, c) cin >> ns[i][j];
    per = per + per;
    m <<= 1;

    int ecnt = 0, wcnt = 0;
    F0R(i, m) {
        if (per[i] == 'E') ecnt++;
        else {
            le = max(le, ecnt);
            ecnt = 0;
        }

        if (per[i] == 'W') wcnt++;
        else {
            lw = max(lw, wcnt);
            wcnt = 0;
        }
    }
    le = max(le, ecnt);
    lw = max(lw, wcnt);

    if (le == m) le = INF;
    if (lw == m) lw = INF;

    F0R(i, r) F0R(j, c) {
        effect[i][j][EAST] = (le >= ns[i][j] && ns[i][j] && j < c - 1);
        effect[i][j][WEST] = (lw >= ns[i][j] && ns[i][j] && j);
    }

    F0R(i, r) {
        FOR(j, 1, c) {
            if (!ns[i][j]) continue;
            if (!effect[i][j - 1][EAST]) lps[i][j] = 0;
            else lps[i][j] = lps[i][j - 1] + 1;
        }

        R0F(j, c - 1) {
            if (!ns[i][j]) continue;
            if (!effect[i][j + 1][WEST]) rps[i][j] = 0;
            else rps[i][j] = rps[i][j + 1] + 1;
        }
    }

    int minim = INF, cnt = 1;
    
    /*
    cout << endl << endl << "_-----------------------------_" << endl;
    F0R(i, r) {
        F0R(j, c) cout << lps[i][j] << ' ';
        cout << endl;
    }
    */

    F0R(i, r) F0R(j, c) {
        if (!ns[i][j]) continue;
        if (minim == lps[i][j] + rps[i][j] + 1) cnt++;
        if (minim > lps[i][j] + rps[i][j] + 1) cnt = 1;
        minim = min(minim, lps[i][j] + rps[i][j] + 1);
    }
#define endl '\n'
    cout << minim << endl << cnt << endl;
}

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