Submission #489535

#	Time	Username	Problem	Language	Result	Execution time	Memory
489535		8e7	Virus Experiment (JOI19_virus)	C++17	14 / 100	85 ms	19500 KiB

virus

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 805
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
bool poss[maxn][maxn][16];
bool done[maxn][maxn], vis[maxn][maxn], col[maxn][maxn];
int ans[maxn][maxn], lef[maxn][maxn], rig[maxn][maxn];
int u[maxn][maxn], ds[100005], dt[100005];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // NESW
int r, c;
inline bool in(int x, int y){return x >= 0 && x < r && y >= 0 && y < c;}
bool con(int x, int y) {
	int mask = 0;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (in(dx, dy)) mask += col[dx][dy] ? (1<<i) : 0;
	}
	return poss[x][y][mask];
}

int main() {
	io
	int m;
	cin >> m >> r >> c;
	string D;
	cin >> D;
	for (int i = 0;i < m;i++) ds[i] = (D[i] == 'N' ? 0 : (D[i] == 'E' ? 1 : (D[i] == 'S' ? 2 : 3)));
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) cin >> u[i][j];
	}
	for (int ti = 0;ti < 16;ti++) {
		int ma = 0, cur = 0, tot = 0, pref = 0, suf = 0;
		for (int i = 0;i < m;i++) {
			if (ti & (1<<ds[i])) {
				dt[i] = 1;
			} else {
				ma = max(ma, cur);
				cur = 0;
				dt[i] = 0;
			}
			cur += dt[i];
			tot += dt[i];
		}
		if (tot == m) {
			ma = 1<<30;	
		} else {
			for (int i = 0;i < m;i++) {
				if (!dt[i]) {
					pref = i;
					break;
				}
			}
			for (int i = m - 1;i >= 0;i--) {
				if (!dt[i]) {
					suf = m - 1 - i;
					break;
				}
			}
			ma = max(ma, pref + suf);
		}
		//debug(ma);
		for (int i = 0;i < r;i++) {
			for (int j = 0;j < c;j++) {
				poss[i][j][ti] = u[i][j] <= ma;
				if (u[i][j] == 0) poss[i][j][ti] = 0;
			}
		}
	}
	for (int i = 0;i < r;i++) {
		int cur = 0;
		for (int j = 0;j < c;j++) {
			if (j) {
				col[i][j] = 1;
				if (!con(i, j-1)) cur = 0;
				col[i][j] = 0;
			}
			cur++;
			lef[i][j] = cur;
		}
		cur = 0;
		for (int j = c - 1;j >= 0;j--) {
			if (j < c - 1) {
				col[i][j] = 1;
				if (!con(i, j+1)) cur = 0;
				col[i][j] = 0;
			}
			cur++;
			rig[i][j] = cur;
		}
	}
	int out = 1<<30, outn = 0;
	for (int i = 0;i < r;i++) {
		for (int j= 0;j < c;j++) {
			if (u[i][j]) {
				//debug(i, j, lef[i][j], rig[i][j]);
				if (lef[i][j] + rig[i][j] < out) out = lef[i][j] + rig[i][j], outn = 1;
				else if (lef[i][j] + rig[i][j] == out) outn++;
			}
		}
	}
	cout << out-1 << "\n" << outn << "\n";
}
/*

7 3 4
EEEWWWE
1 1 0 1
1 0 1 3
1 1 1 1
*/

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