#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<long double, ll> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 8e2 + 5, maxm = 1e5+5, lg = 10, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int m, r, c, u[maxn][maxn], a[maxm];
int cnt[16], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
pp ans = {inf, 0};
void as(int x){
if(x < ans.ff) ans = {x, 1};
else if(x == ans.ff) ans.ss++;
}
void slv1(){
rep(i,0,r){
vector<int> lx(c), rx(c);
rep(j,0,c){
if(!u[i][j]) continue;
lx[j] = j;
if(j && u[i][j-1] && u[i][j-1] <= cnt[2]) lx[j] = lx[j-1];
}
per(j,c-1,0){
if(!u[i][j]) continue;
rx[j] = j;
if(j < c-1 && u[i][j+1] && u[i][j+1] <= cnt[8]) rx[j] = rx[j+1];
}
rep(j,0,c){
if(u[i][j]) as(rx[j] - lx[j] + 1);
}
}
}
void slv2(){
rep(i,0,r){
rep(j,0,c){
if(!u[i][j]) continue;
vector<vector<int>> st(r, vector<int>(c));
vector<vector<bool>> vis(r, vector<bool>(c));
auto chk = [&](int i, int j){
return !vis[i][j] && u[i][j] && cnt[st[i][j]] >= u[i][j];
};
int cnt = 0;
function<void(int, int)> dfs = [&](int i, int j){
vis[i][j] = true, cnt++;
rep(d,0,4){
int x = i+dx[d], y = j+dy[d];
if(x < 0 || x >= r || y < 0 || y >= c) continue;
int f = (d + 2)%4;
st[x][y] ^= 1<<f;
if(chk(x, y)) dfs(x, y);
}
}; dfs(i, j);
as(cnt);
}
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
string s; cin >> m >> r >> c >> s;
rep(i,0,m){
if(s[i] == 'E') a[i] = 1;
if(s[i] == 'S') a[i] = 2;
if(s[i] == 'W') a[i] = 3;
}
rep(i,0,r) rep(j,0,c) cin >> u[i][j];
rep(i,0,16){
vector<bool> is(4);
rep(j,0,4) if(i>>j&1) is[j] = true;
int f = -1;
rep(j,0,m) if(!is[a[j]]) f = j;
if(f == -1) cnt[i] = inf;
else{
int mx = 0, cr = 0;
int pos = f;
do{
if(is[a[f]]) cr++;
else mx = max(mx, cr), cr = 0;
f = (f + 1)%m;
}while(pos - f); mx = max(mx, cr);
cnt[i] = mx;
}
}
if(max(r, c) <= 50) slv2();
else slv1();
cout << ans.ff << '\n' << ans.ss << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
688 KB |
Output is correct |
2 |
Correct |
58 ms |
2852 KB |
Output is correct |
3 |
Correct |
53 ms |
2836 KB |
Output is correct |
4 |
Correct |
35 ms |
2808 KB |
Output is correct |
5 |
Correct |
50 ms |
2776 KB |
Output is correct |
6 |
Correct |
1 ms |
2772 KB |
Output is correct |
7 |
Correct |
51 ms |
3532 KB |
Output is correct |
8 |
Correct |
39 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
7 ms |
596 KB |
Output is correct |
3 |
Correct |
21 ms |
1052 KB |
Output is correct |
4 |
Correct |
9 ms |
980 KB |
Output is correct |
5 |
Correct |
20 ms |
1028 KB |
Output is correct |
6 |
Correct |
349 ms |
1376 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
22 ms |
1108 KB |
Output is correct |
9 |
Correct |
153 ms |
516 KB |
Output is correct |
10 |
Correct |
7 ms |
980 KB |
Output is correct |
11 |
Correct |
37 ms |
468 KB |
Output is correct |
12 |
Correct |
388 ms |
600 KB |
Output is correct |
13 |
Correct |
193 ms |
1108 KB |
Output is correct |
14 |
Correct |
179 ms |
1108 KB |
Output is correct |
15 |
Correct |
192 ms |
1228 KB |
Output is correct |
16 |
Correct |
181 ms |
1192 KB |
Output is correct |
17 |
Correct |
41 ms |
852 KB |
Output is correct |
18 |
Correct |
46 ms |
468 KB |
Output is correct |
19 |
Correct |
57 ms |
1116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
688 KB |
Output is correct |
2 |
Correct |
58 ms |
2852 KB |
Output is correct |
3 |
Correct |
53 ms |
2836 KB |
Output is correct |
4 |
Correct |
35 ms |
2808 KB |
Output is correct |
5 |
Correct |
50 ms |
2776 KB |
Output is correct |
6 |
Correct |
1 ms |
2772 KB |
Output is correct |
7 |
Correct |
51 ms |
3532 KB |
Output is correct |
8 |
Correct |
39 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
7 ms |
596 KB |
Output is correct |
11 |
Correct |
21 ms |
1052 KB |
Output is correct |
12 |
Correct |
9 ms |
980 KB |
Output is correct |
13 |
Correct |
20 ms |
1028 KB |
Output is correct |
14 |
Correct |
349 ms |
1376 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
22 ms |
1108 KB |
Output is correct |
17 |
Correct |
153 ms |
516 KB |
Output is correct |
18 |
Correct |
7 ms |
980 KB |
Output is correct |
19 |
Correct |
37 ms |
468 KB |
Output is correct |
20 |
Correct |
388 ms |
600 KB |
Output is correct |
21 |
Correct |
193 ms |
1108 KB |
Output is correct |
22 |
Correct |
179 ms |
1108 KB |
Output is correct |
23 |
Correct |
192 ms |
1228 KB |
Output is correct |
24 |
Correct |
181 ms |
1192 KB |
Output is correct |
25 |
Correct |
41 ms |
852 KB |
Output is correct |
26 |
Correct |
46 ms |
468 KB |
Output is correct |
27 |
Correct |
57 ms |
1116 KB |
Output is correct |
28 |
Incorrect |
60 ms |
4740 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |