# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
818737 |
2023-08-10T06:34:40 Z |
반딧불(#10131) |
바이러스 (JOI19_virus) |
C++17 |
|
2000 ms |
3428 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1}, cc[]={'S', 'E', 'N', 'W'};
int n, m, k;
int str[200002];
int maxLen[16];
int arr[802][802];
bool col[802][802];
int solve(int sx, int sy){
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) col[i][j] = 0;
queue<pair<int, int> > que;
col[sx][sy] = 1, que.push(make_pair(sx, sy));
int cnt = 0;
while(!que.empty()){
int x = que.front().first, y = que.front().second; que.pop();
cnt++;
for(int d=0; d<4; d++){
int tx=x+xx[d], ty=y+yy[d], ts = 0;
if(tx<1 || tx>n || ty<1 || ty>m || !arr[tx][ty] || col[tx][ty]) continue;
for(int dd=0; dd<4; dd++){
int ttx = tx+xx[dd], tty=ty+yy[dd];
if(col[ttx][tty]) ts += (1<<dd);
}
if(arr[tx][ty] <= maxLen[ts]) col[tx][ty] = 1, que.push(make_pair(tx, ty));
}
}
return cnt;
}
int main(){
scanf("%d %d %d", &k, &n, &m);
for(int i=1; i<=k; i++){
char c;
scanf(" %c", &c);
if(c=='S') str[i] = 0;
if(c=='E') str[i] = 1;
if(c=='N') str[i] = 2;
if(c=='W') str[i] = 3;
str[i+k]=str[i];
}
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &arr[i][j]);
for(int d=0; d<16; d++){
int cnt = 0;
for(int i=1; i<=k*2; i++){
if((d>>str[i])&1) cnt++, maxLen[d] = max(maxLen[d], cnt);
else cnt = 0;
}
if(maxLen[d] == k*2) maxLen[d] = 100002;
}
int ans = INT_MAX, ansCnt = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(!arr[i][j]) continue;
int v = solve(i, j);
if(ans > v) ans = v, ansCnt = 1;
else if(ans == v) ansCnt++;
}
}
printf("%d\n%d", ans, ansCnt);
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d %d %d", &k, &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
virus.cpp:47:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &arr[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
704 KB |
Output is correct |
2 |
Execution timed out |
2070 ms |
3428 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
6 ms |
1108 KB |
Output is correct |
3 |
Correct |
14 ms |
1132 KB |
Output is correct |
4 |
Correct |
8 ms |
1108 KB |
Output is correct |
5 |
Correct |
14 ms |
980 KB |
Output is correct |
6 |
Correct |
140 ms |
1268 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
14 ms |
1248 KB |
Output is correct |
9 |
Correct |
75 ms |
476 KB |
Output is correct |
10 |
Correct |
6 ms |
1108 KB |
Output is correct |
11 |
Correct |
4 ms |
468 KB |
Output is correct |
12 |
Correct |
233 ms |
468 KB |
Output is correct |
13 |
Correct |
79 ms |
1284 KB |
Output is correct |
14 |
Correct |
76 ms |
1264 KB |
Output is correct |
15 |
Correct |
80 ms |
1268 KB |
Output is correct |
16 |
Correct |
68 ms |
1272 KB |
Output is correct |
17 |
Correct |
9 ms |
852 KB |
Output is correct |
18 |
Correct |
8 ms |
468 KB |
Output is correct |
19 |
Correct |
15 ms |
1248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
704 KB |
Output is correct |
2 |
Execution timed out |
2070 ms |
3428 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |