oj.uz

Submission #261353

# Submission time Handle Problem Language Result Execution time Memory
261353 2020-08-11T16:30:19 Z limabeans Virus Experiment (JOI19_virus) C++17
0 / 100
 2000 ms 22188 KB 
#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));


    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);
	    if ((int)stat[i][j].size() >= g[i][j]) {
		has[i][j] = true;
		stat[i][j].clear();
	    }
	} else {
	    stat[i][j].clear();
	    stat[i][j].push_back(time);
	}
    };

    int len = s.length();
    for (int iter=0; iter<1000; iter++) {
	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);
		    }
		}	
	    }
	}
    }

    // 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.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 632 KB Output is correct
2 Execution timed out 2090 ms 22188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 25 ms 768 KB Output is correct
3 Incorrect 37 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 632 KB Output is correct
2 Execution timed out 2090 ms 22188 KB Time limit exceeded
3 Halted 0 ms 0 KB -