#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#define F first
#define S second
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
using namespace std;
string tb(ll x)
{
string s = "";
while(x>0)
{
if(x&1)
s+='1';
else
s+='0';
x/=2;
}
while(s.size()<4)
s+='0';
return s;
}
int main()
{
d3
int m;
int16_t r,c;
string d;
cin >> m >> r >> c;
cin >> d;
int a[r+1][c+1];
int b[2][2][2][2];
for(int16_t i = 1 ; r>=i ; i++)
for(int16_t j = 1 ; c>=j ; j++)
{
cin >> a[i][j];
if(a[i][j]==0)
a[i][j]=1e5+1;
}
d+=d;
for(int8_t i = 1 ; 16>=i ; i++)
{
string s = tb(i);
bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
if(s[0]=='1')
l1=1;
if(s[1]=='1')
l2=1;
if(s[2]=='1')
l3=1;
if(s[3]=='1')
l4=1;
int lon = 0;
int cur = 0;
for(int j = 0 ; d.size()>j ; j++)
{
if((d[j]=='S'&&l1)||(d[j]=='N'&&l2)||(d[j]=='E'&&l3)||(d[j]=='W'&&l4))
{
cur++;
continue;
}
lon=max(lon,cur);
cur=0;
}
lon=max(lon,cur);
if(lon==2*m)
lon=1e5;
b[l1][l2][l3][l4]=lon;
}
int mn = 1e6;
int ans = 0;
pair<int,int> A[r*c];
for(int i = 1 ; r>=i ; i++)
for(int j = 1 ; c>=j ; j++)
A[(i-1)*c+j-1]={i,j};
random_shuffle(A,A+r*c);
bool infected[r+2][c+2];
bool tak[r+1][c+1];
memset(tak,0,sizeof(tak));
for(int iiii = 0 ; r*c>iiii ; iiii++)
{
int16_t x = A[iiii].F;
int16_t y = A[iiii].S;
if(a[x][y]>1e5)
continue;
memset(infected,0,sizeof(infected));
queue<pair<int16_t,int16_t>> q;
q.push({x,y});
bool ge = 0;
int mn1 = 0;
while(!q.empty())
{
pair<int16_t,int16_t> nod = q.front();
q.pop();
if(infected[nod.F][nod.S])
continue;
infected[nod.F][nod.S]=1;
mn1++;
if(mn1>mn)
break;
for(int8_t ii = 0 ; 4>ii ; ii++)
{
int16_t xx = nod.F , yy = nod.S;
if(ii==1)
xx++;
else if(ii==2)
xx--;
else if(ii==3)
yy++;
else
yy--;
if(xx<1||xx>r||yy<1||yy>c||infected[xx][yy])
continue;
bool l1 = 0 , l2 = 0 , l3 = 0 , l4 = 0;
if(infected[xx+1][yy])
l1=1;
if(infected[xx-1][yy])
l2=1;
if(infected[xx][yy+1])
l3=1;
if(infected[xx][yy-1])
l4=1;
if(b[l1][l2][l3][l4]>=a[xx][yy])
{
if(tak[xx][yy])
{
ge=1;
break;
}
q.push({xx,yy});
}
}
if(ge)
break;
}
tak[x][y]=1;
if(ge)
continue;
if(mn1==mn)
ans++;
if(mn1<mn)
{
ans=1;
mn=mn1;
}
}
cout << mn << "\n" << ans*mn;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:59:33: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | for(int j = 0 ; d.size()>j ; j++)
| ~~~~~~~~^~
virus.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
77 | for(int i = 1 ; r>=i ; i++)
| ^~~
virus.cpp:80:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
80 | random_shuffle(A,A+r*c);
| ^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
2051 ms |
9300 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
860 KB |
Output is correct |
| 3 |
Correct |
19 ms |
860 KB |
Output is correct |
| 4 |
Correct |
3 ms |
860 KB |
Output is correct |
| 5 |
Correct |
19 ms |
856 KB |
Output is correct |
| 6 |
Correct |
20 ms |
860 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
19 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
860 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Correct |
19 ms |
860 KB |
Output is correct |
| 14 |
Correct |
19 ms |
860 KB |
Output is correct |
| 15 |
Correct |
18 ms |
856 KB |
Output is correct |
| 16 |
Correct |
19 ms |
856 KB |
Output is correct |
| 17 |
Correct |
10 ms |
604 KB |
Output is correct |
| 18 |
Correct |
2 ms |
348 KB |
Output is correct |
| 19 |
Correct |
19 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
2051 ms |
9300 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
