#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 805;
int mx[16];
char dir[4] = {'S','N','E','W'};
int di[4][2] = {{-1,0},{+1,0},{0,-1},{0,+1}};
int U[N][N];
void shuffle(vector<pii> &ord){
int sz = ord.size();
int ii, jj;
for(int pi = 0; pi < 4 * sz; pi ++ ){
ii = ((int)rng() % sz + sz) % sz;
jj = ((int)rng() % sz + sz) % sz;
swap(ord[ii], ord[jj]);
}
}
bool mark[N][N];
bool vis[N][N];
int bits[N][N];
int low = (int)1e9;
int how = 0;
void bfs(int pi, int qi){
queue<pii> que;
que.push(mp(pi, qi));
mark[pi][qi]=true;
vis[pi][qi]=true;
vector<pii> delet;
delet.push_back(mp(pi,qi));
int total = 0;
int ni, nj;
bool terminate = false;
while(!que.empty() && !terminate){
pi = que.front().fi;
qi = que.front().se;
total ++ ;
que.pop();
for(int d = 0; d < 4; d ++ ){
ni = pi + di[d][0];
nj = qi + di[d][1];
if(vis[ni][nj]) continue;
delet.push_back(mp(ni, nj));
bits[ni][nj] |= (1 << d);
if(mx[bits[ni][nj]] >= U[ni][nj]){
if(mark[ni][nj]){
terminate = true;
break;
}
vis[ni][nj] = true;
que.push(mp(ni,nj));
}
}
}
for(auto x : delet){
vis[x.fi][x.se] = false;
bits[x.fi][x.se] = false;
}
if(!terminate){
if(total < low){
low = total;
how = 0;
}
if(total == low){
how += low;
}
}
}
int main(){
fastIO;
//freopen("in.txt","r",stdin);
int n, m, l;
cin >> l >> n >> m;
string s;
cin >> s;
string res = "";
for(int i = 0 ; i < N; i ++ ){
for(int j = 0 ; j < N ; j ++ ){
U[i][j] = (int)1e9;
}
}
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m; j ++ ){
cin >> U[i][j];
if(U[i][j] == 0)
U[i][j] = (int)1e9;
}
}
while(res.size() < (int)2e5){
for(int i = 0 ; i < l; i ++ ){
res.push_back(s[i]);
}
}
bool match;
int cnt;
for(int mask = 0 ; mask < 16 ; mask ++ ){
cnt = 0;
for(char x : res){
match = false;
for(int j = 0 ; j < 4; j ++ ){
if(dir[j] == x && (mask & (1 << j))){
match = true;
}
}
if(match){
cnt ++ ;
mx[mask] = max(mx[mask],cnt);
}
else{
cnt = 0;
}
}
}
vector<pii> ord;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= m ; j ++ ){
if(U[i][j] < (int)1e9){
ord.push_back(mp(i,j));
}
}
}
shuffle(ord);
for(auto x : ord){
bfs(x.fi, x.se);
}
cout << low << "\n" << how << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
3320 KB |
Output is correct |
2 |
Correct |
430 ms |
13236 KB |
Output is correct |
3 |
Correct |
625 ms |
15496 KB |
Output is correct |
4 |
Correct |
656 ms |
13184 KB |
Output is correct |
5 |
Correct |
410 ms |
15656 KB |
Output is correct |
6 |
Correct |
23 ms |
6748 KB |
Output is correct |
7 |
Correct |
639 ms |
13552 KB |
Output is correct |
8 |
Correct |
142 ms |
8964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
3204 KB |
Output is correct |
2 |
Correct |
20 ms |
3520 KB |
Output is correct |
3 |
Correct |
40 ms |
3480 KB |
Output is correct |
4 |
Correct |
21 ms |
3520 KB |
Output is correct |
5 |
Correct |
39 ms |
3500 KB |
Output is correct |
6 |
Correct |
39 ms |
3628 KB |
Output is correct |
7 |
Correct |
28 ms |
3200 KB |
Output is correct |
8 |
Correct |
41 ms |
3632 KB |
Output is correct |
9 |
Correct |
28 ms |
3332 KB |
Output is correct |
10 |
Correct |
18 ms |
3516 KB |
Output is correct |
11 |
Correct |
29 ms |
3340 KB |
Output is correct |
12 |
Correct |
30 ms |
3336 KB |
Output is correct |
13 |
Correct |
42 ms |
3632 KB |
Output is correct |
14 |
Correct |
37 ms |
3728 KB |
Output is correct |
15 |
Correct |
38 ms |
3632 KB |
Output is correct |
16 |
Correct |
39 ms |
3728 KB |
Output is correct |
17 |
Correct |
42 ms |
3472 KB |
Output is correct |
18 |
Correct |
38 ms |
3412 KB |
Output is correct |
19 |
Correct |
42 ms |
3728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
3320 KB |
Output is correct |
2 |
Correct |
430 ms |
13236 KB |
Output is correct |
3 |
Correct |
625 ms |
15496 KB |
Output is correct |
4 |
Correct |
656 ms |
13184 KB |
Output is correct |
5 |
Correct |
410 ms |
15656 KB |
Output is correct |
6 |
Correct |
23 ms |
6748 KB |
Output is correct |
7 |
Correct |
639 ms |
13552 KB |
Output is correct |
8 |
Correct |
142 ms |
8964 KB |
Output is correct |
9 |
Correct |
21 ms |
3204 KB |
Output is correct |
10 |
Correct |
20 ms |
3520 KB |
Output is correct |
11 |
Correct |
40 ms |
3480 KB |
Output is correct |
12 |
Correct |
21 ms |
3520 KB |
Output is correct |
13 |
Correct |
39 ms |
3500 KB |
Output is correct |
14 |
Correct |
39 ms |
3628 KB |
Output is correct |
15 |
Correct |
28 ms |
3200 KB |
Output is correct |
16 |
Correct |
41 ms |
3632 KB |
Output is correct |
17 |
Correct |
28 ms |
3332 KB |
Output is correct |
18 |
Correct |
18 ms |
3516 KB |
Output is correct |
19 |
Correct |
29 ms |
3340 KB |
Output is correct |
20 |
Correct |
30 ms |
3336 KB |
Output is correct |
21 |
Correct |
42 ms |
3632 KB |
Output is correct |
22 |
Correct |
37 ms |
3728 KB |
Output is correct |
23 |
Correct |
38 ms |
3632 KB |
Output is correct |
24 |
Correct |
39 ms |
3728 KB |
Output is correct |
25 |
Correct |
42 ms |
3472 KB |
Output is correct |
26 |
Correct |
38 ms |
3412 KB |
Output is correct |
27 |
Correct |
42 ms |
3728 KB |
Output is correct |
28 |
Correct |
661 ms |
25068 KB |
Output is correct |
29 |
Correct |
707 ms |
25008 KB |
Output is correct |
30 |
Correct |
627 ms |
19700 KB |
Output is correct |
31 |
Correct |
650 ms |
16860 KB |
Output is correct |
32 |
Correct |
649 ms |
16112 KB |
Output is correct |
33 |
Correct |
485 ms |
13240 KB |
Output is correct |
34 |
Correct |
672 ms |
25652 KB |
Output is correct |
35 |
Correct |
495 ms |
18884 KB |
Output is correct |
36 |
Correct |
545 ms |
13496 KB |
Output is correct |
37 |
Correct |
649 ms |
19432 KB |
Output is correct |
38 |
Correct |
558 ms |
24784 KB |
Output is correct |
39 |
Correct |
392 ms |
14368 KB |
Output is correct |
40 |
Correct |
532 ms |
14392 KB |
Output is correct |
41 |
Correct |
474 ms |
12936 KB |
Output is correct |
42 |
Correct |
610 ms |
19564 KB |
Output is correct |
43 |
Correct |
578 ms |
19836 KB |
Output is correct |
44 |
Correct |
167 ms |
8936 KB |
Output is correct |