Submission #147243

#	Time	Username	Problem	Language	Result	Execution time	Memory
147243		Alexa2001	Virus Experiment (JOI19_virus)	C++17	14 / 100	77 ms	6652 KiB

virus

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 808, inf = 1e9;

int a[Nmax][Nmax];
string moves;
int goW[Nmax], goE[Nmax], maxE, maxW;
int L, N, M;

void solve(int &best, int &cnt, int a[])
{
    int i;

    goW[1] = (a[1] != inf);
    for(i=2; i<=M; ++i)
    {
        goW[i] = (maxE >= a[i-1] ? goW[i-1] : 0) + 1;
        if(a[i] == inf) goW[i] = 0;
    }

    goE[M] = (a[M] != inf);
    for(i=M-1; i>=1; --i)
    {
        goE[i] = (maxW >= a[i+1] ? goE[i+1] : 0) + 1;
        if(a[i] == inf) goE[i] = 0;
    }

    for(i=1; i<=M; ++i)
    {
        if(a[i] == inf) continue;

        int curr = goE[i] + goW[i] - 1;
        if(curr < best) best = curr, cnt = 1;
            else if(curr == best) ++cnt;
    }
}

void solve1()
{
    int i, nr; maxE = 0, maxW = 0;

    nr = 0;
    for(i=0; i<L; ++i)
    {
        if(moves[i] == 'E') ++nr;
            else maxE = max(maxE, nr), nr = 0;
    }
    for(i=0; i<L; ++i) 
        if(moves[i] == 'E') ++nr;
            else break;
    maxE = max(maxE, nr); 
    if(maxE == 2*L) maxE = inf - 10;

    nr = 0;
    for(i=0; i<L; ++i)
    {
        if(moves[i] == 'W') ++nr;
            else maxW = max(maxW, nr), nr = 0;
    }
    for(i=0; i<L; ++i) 
        if(moves[i] == 'W') ++nr;
            else break;
    maxW = max(maxW, nr); 
    if(maxW == 2*L) maxW = inf - 10;
    
    int best = inf, cnt = 0;
    for(i=1; i<=N; ++i)
        solve(best, cnt, a[i]);

    cout << best << '\n' << cnt << '\n';
}

int main()
{
  //  freopen("virus.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> L >> N >> M;
    cin >> moves;

    int i, j;
    for(i=1; i<=N; ++i)
        for(j=1; j<=M; ++j)
        {
            cin >> a[i][j];
            if(a[i][j] == 0) a[i][j] = inf;
        }

     solve1();
   // solve2();

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80