#include "bits/stdc++.h"
using namespace std;
#define ar array
//~ #define int long long
signed main(){
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios::sync_with_stdio(0); cin.tie(0);
int k, n, m; cin>>k>>n>>m;
string s; cin>>s;
s += s;
vector<int> mx(1 << 4, 0), cur(1 << 4, 0);
for(int i=0;i<2*k;i++){
int c = 0;
if(s[i] == 'N') c = 0;
if(s[i] == 'E') c = 1;
if(s[i] == 'S') c = 2;
if(s[i] == 'W') c = 3;
for(int mask=0;mask<16;mask++){
if(mask >> c & 1) cur[mask]++;
else cur[mask] = 0;
mx[mask] = max(mx[mask], cur[mask]);
}
}
for(int i=0;i<16;i++){
if(mx[i] >= k) mx[i] = 1e9 + 7;
}
vector<vector<int>> a(n, vector<int>(m));
vector<int> ord;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
if(a[i][j]) ord.push_back(i * m + j);
}
}
shuffle(ord.begin(), ord.end(), rng);
int res = 1e9, cnt = 0;
vector<vector<int>> t(n, vector<int>(m)), used(n, vector<int>(m));
int tt = 0;
for(auto x : ord) t[x/m][x%m] = ++tt;
int ch[4][2] = {
{-1, 0},
{0, 1},
{1, 0},
{0, -1}
};
auto check = [&](int i, int j){
if(!(0 <= i && i < n && 0 <= j && j < m) || a[i][j] == 0) return false;
int tot = 0;
for(int t=0;t<4;t++){
int x = i + ch[t][0], y = j + ch[t][1];
if(0 <= x && x < n && 0 <= y && y < m && used[x][y]) tot |= (1 << t);
}
return (mx[tot] >= a[i][j]);
};
for(auto x : ord){
int i = x/m, j = x%m;
vector<int> tot; tot.push_back(x);
queue<int> qq; qq.push(x);
used[i][j] = 1;
bool flag = 1;
while(!qq.empty() && flag){
int x = qq.front() / m, y = qq.front() % m; qq.pop();
for(int k=0;k<4;k++){
int r = x + ch[k][0], c = y + ch[k][1];
if(check(r, c) && !used[r][c]) {
used[r][c] = 1, qq.push(r * m + c);
tot.push_back(r * m + c);
if(t[r][c] < t[i][j]) { flag = 0; break; }
}
}
}
for(auto x : tot) used[x/m][x%m] = 0;
if(!flag) continue;
int sz = (int)tot.size();
if(sz < res) res = sz, cnt = 0;
cnt += (sz == res);
}
cout<<res<<"\n"<<cnt * res<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
440 KB |
Output is correct |
2 |
Correct |
299 ms |
11676 KB |
Output is correct |
3 |
Correct |
584 ms |
13948 KB |
Output is correct |
4 |
Correct |
540 ms |
11692 KB |
Output is correct |
5 |
Correct |
226 ms |
14160 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
532 ms |
11992 KB |
Output is correct |
8 |
Correct |
65 ms |
5788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
744 KB |
Output is correct |
3 |
Correct |
7 ms |
716 KB |
Output is correct |
4 |
Correct |
5 ms |
716 KB |
Output is correct |
5 |
Correct |
7 ms |
716 KB |
Output is correct |
6 |
Correct |
9 ms |
764 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
8 ms |
804 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
5 ms |
708 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
3 ms |
316 KB |
Output is correct |
13 |
Correct |
7 ms |
752 KB |
Output is correct |
14 |
Correct |
8 ms |
716 KB |
Output is correct |
15 |
Correct |
8 ms |
792 KB |
Output is correct |
16 |
Correct |
8 ms |
836 KB |
Output is correct |
17 |
Correct |
5 ms |
452 KB |
Output is correct |
18 |
Correct |
2 ms |
312 KB |
Output is correct |
19 |
Correct |
7 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
440 KB |
Output is correct |
2 |
Correct |
299 ms |
11676 KB |
Output is correct |
3 |
Correct |
584 ms |
13948 KB |
Output is correct |
4 |
Correct |
540 ms |
11692 KB |
Output is correct |
5 |
Correct |
226 ms |
14160 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
532 ms |
11992 KB |
Output is correct |
8 |
Correct |
65 ms |
5788 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
5 ms |
744 KB |
Output is correct |
11 |
Correct |
7 ms |
716 KB |
Output is correct |
12 |
Correct |
5 ms |
716 KB |
Output is correct |
13 |
Correct |
7 ms |
716 KB |
Output is correct |
14 |
Correct |
9 ms |
764 KB |
Output is correct |
15 |
Correct |
1 ms |
320 KB |
Output is correct |
16 |
Correct |
8 ms |
804 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
5 ms |
708 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
316 KB |
Output is correct |
21 |
Correct |
7 ms |
752 KB |
Output is correct |
22 |
Correct |
8 ms |
716 KB |
Output is correct |
23 |
Correct |
8 ms |
792 KB |
Output is correct |
24 |
Correct |
8 ms |
836 KB |
Output is correct |
25 |
Correct |
5 ms |
452 KB |
Output is correct |
26 |
Correct |
2 ms |
312 KB |
Output is correct |
27 |
Correct |
7 ms |
844 KB |
Output is correct |
28 |
Correct |
875 ms |
18408 KB |
Output is correct |
29 |
Correct |
820 ms |
18132 KB |
Output is correct |
30 |
Correct |
778 ms |
15188 KB |
Output is correct |
31 |
Correct |
726 ms |
12592 KB |
Output is correct |
32 |
Correct |
759 ms |
12328 KB |
Output is correct |
33 |
Correct |
357 ms |
11796 KB |
Output is correct |
34 |
Correct |
860 ms |
17780 KB |
Output is correct |
35 |
Correct |
618 ms |
12080 KB |
Output is correct |
36 |
Correct |
684 ms |
12204 KB |
Output is correct |
37 |
Correct |
845 ms |
13864 KB |
Output is correct |
38 |
Correct |
873 ms |
18192 KB |
Output is correct |
39 |
Correct |
321 ms |
12896 KB |
Output is correct |
40 |
Correct |
354 ms |
12860 KB |
Output is correct |
41 |
Correct |
299 ms |
11648 KB |
Output is correct |
42 |
Correct |
725 ms |
14344 KB |
Output is correct |
43 |
Correct |
817 ms |
15704 KB |
Output is correct |
44 |
Correct |
67 ms |
5848 KB |
Output is correct |