Submission #261368

#	Time	Username	Problem	Language	Result	Execution time	Memory
261368		limabeans	Virus Experiment (JOI19_virus)	C++17	0 / 100	2081 ms	512 KiB

virus

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 801;
const int inf = 2e9;


int m,r,c;
string s;
vector<vector<int>> g;


int sim(int x, int y, vector<vector<int>> g) {
    int n = g.size();
    int m = g[0].size();
    vector<vector<bool>> has(n, vector<bool>(m));
    
    has[x][y]=true;

    vector<vector<vector<int>>> stat(n, vector<vector<int>>(m));

    vector<vector<bool>> _has;

    auto inc = [&](int i, int j, int time) {
	if (has[i][j]) return;
	if (g[i][j]==0) return;
	if (stat[i][j].empty() || stat[i][j].back()+1==time) {
	    stat[i][j].push_back(time);
	} else {
	    stat[i][j].clear();
	    stat[i][j].push_back(time);
	}
	if ((int)stat[i][j].size() >= g[i][j]) {
	    _has[i][j] = true;
	    stat[i][j].clear();
	}
    };

    int len = s.length();
    const int TIMES = 2e5;
    for (int iter=0; iter<TIMES; iter++) {
	_has = has;
	for (int i=0; i<n; i++) {
	    for (int j=0; j<m; j++) {
		char c = s[iter%len];
		
		if (has[i][j]) {
		    if (c=='W' && j+1<m) {
			inc(i,j+1,iter);
		    }
		    if (c=='E' && j>0) {
			inc(i,j-1,iter);
		    }
		    if (c=='S' && i>0) {
			inc(i-1,j,iter);
		    }
		    if (c=='N' && i+1<n) {
			inc(i+1,j,iter);
		    }
		}	
	    }
	}
	has = _has;
    }

    // for (int i=0; i<n; i++) {
    // 	for (int j=0; j<m; j++) {
    // 	    cout<<has[i][j];
    // 	}
    // 	cout<<endl;
    // }


    int res = 0;
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    res += has[i][j];
	}
    }

    return res;
}

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

    cin>>m>>r>>c;
    g = vector<vector<int>>(r, vector<int>(c));
    cin>>s;
    for (int i=0; i<r; i++) {
	for (int j=0; j<c; j++) {
	    cin>>g[i][j];
	}
    }


    map<int,int> mp;

    for (int i=0; i<r; i++) {
	for (int j=0; j<c; j++) {
	    if (g[i][j] > 0) {
		int cur = sim(i,j,g);
		mp[cur]++;
	    }
	}
    }

    cout<<mp.begin()->first<<endl;
    cout<<mp.begin()->second<<endl;
    
    
    return 0;
}

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