Submission #489534

#	Time	Username	Problem	Language	Result	Execution time	Memory
489534		Haruto810198	Virus Experiment (JOI19_virus)	C++17	14 / 100	68 ms	7496 KiB

virus

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// N, S, W, E (from)

int m;
vi str;
int r, c;
int def[810][810];
// immune -> def = INF
int len[16]; // len[mask] = longest substring
// continuous -> len = INF - 1

int res_min, res_cnt;

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m>>r>>c;
	FOR(i, 1, m, 1){
		char ch;
		cin>>ch;
		if(ch == 'N') str.pb(0);
		if(ch == 'S') str.pb(1);
		if(ch == 'W') str.pb(2);
		if(ch == 'E') str.pb(3);
	}
	
	FOR(i, 0, r+1, 1){
		FOR(j, 0, c+1, 1){
			def[i][j] = INF;
		}
	}

	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			cin>>def[i][j];
			if(def[i][j] == 0) def[i][j] = INF;
		}
	}
	
	// find len[]
	FOR(i, 0, m-1, 1){
		str.pb(str[i]);
	}
	
	FOR(mask, 0, 15, 1){
		int cur = 0;
		for(int i : str){
			if(mask & (1<<i)) cur++;
			else cur = 0;
			len[mask] = max(len[mask], cur);
		}
		if(len[mask] == szof(str)) len[mask] = INF - 1;
	}
	
	res_min = INF;
	FOR(i, 1, r, 1){
		int il[810], ir[810];
		
		ir[0] = 0;
		FOR(j, 1, c, 1){
			ir[j] = max(j, ir[j - 1]);
			if(def[i][j] == INF) continue;
			while(ir[j] < c and def[i][ir[j] + 1] <= len[4]){ // W
				ir[j]++;
			}
		}
		
		il[c + 1] = c + 1;
		for(int j = c; j >= 1; j--){
			il[j] = min(j, il[j + 1]);
			if(def[i][j] == INF) continue;
			while(il[j] > 1 and def[i][il[j] - 1] <= len[8]){ // E
				il[j]--;
			}
		}
			
		FOR(j, 1, c, 1){
			if(def[i][j] == INF){
				continue;
			}
			int cnt = ir[j] - il[j] + 1;
			if(cnt < res_min){
				res_min = cnt;
				res_cnt = 1;
			}
			else if(cnt == res_min){
				res_cnt++;
			}
		}
	}
	
	cout<<res_min<<'\n'<<res_cnt<<'\n';
	
	return 0;

}

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