oj.uz

Submission #818733

# Submission time Handle Problem Language Result Execution time Memory
818733 2023-08-10T06:33:24 Z 반딧불(#10131) Virus Experiment (JOI19_virus) C++17
14 / 100
 90 ms 3576 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 crev[128];

int n, m, k;
int str[200002];
int maxLen[16];
int arr[802][802];

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++){
        vector<int> limp, rimp;
        for(int j=0; j<=m+1; j++){
            if(arr[i][j] == 0 || arr[i][j] > maxLen[2]) limp.push_back(j);
            if(arr[i][j] == 0 || arr[i][j] > maxLen[8]) rimp.push_back(j);
        }

        for(int j=1; j<=m; j++){
            if(arr[i][j] == 0) continue;
            int a = *prev(lower_bound(limp.begin(), limp.end(), j));
            int b = *upper_bound(rimp.begin(), rimp.end(), j);
            if(b-a-1 < ans) ans = b-a-1, ansCnt = 1;
            else if(b-a-1 == ans) ansCnt++;
        }
    }
    printf("%d\n%d", ans, ansCnt);
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d %d %d", &k, &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
virus.cpp:25:58: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &arr[i][j]);
      |                                                     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 90 ms 2816 KB Output is correct
3 Correct 68 ms 2796 KB Output is correct
4 Correct 52 ms 2768 KB Output is correct
5 Correct 84 ms 2888 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 54 ms 3576 KB Output is correct
8 Correct 41 ms 2632 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 90 ms 2816 KB Output is correct
3 Correct 68 ms 2796 KB Output is correct
4 Correct 52 ms 2768 KB Output is correct
5 Correct 84 ms 2888 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 54 ms 3576 KB Output is correct
8 Correct 41 ms 2632 KB Output is correct
9 Incorrect 0 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -