Submission #1010701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010701		vivkostov	Virus Experiment (JOI19_virus)	C++14	6 / 100	2033 ms	27664 KiB

virus

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct cell
{
    int a,b;
};
int k,n,m,a[1005][1005],ma[2][2][2][2],used[1005][1005],otg,maa=1000000000,win[1005][1005][5];
string s;
void prec()
{
    int h=0,fir=-1;
    for(int i1=0;i1<=1;i1++)
    {
        for(int i2=0;i2<=1;i2++)
        {
            for(int i3=0;i3<=1;i3++)
            {
                for(int i4=0;i4<=1;i4++)
                {
                    for(int j=0;j<k;j++)
                    {
                        int p=ma[i1][i2][i3][i4];
                        if(s[j]=='S')
                        {
                            if(i1==1)
                            {
                                h++;
                                ma[i1][i2][i3][i4]=max(p,h);
                            }
                            else
                            {
                                if(fir==-1)fir=h;
                                h=0;
                            }
                        }
                        if(s[j]=='W')
                        {
                            if(i2==1)
                            {
                                h++;
                                ma[i1][i2][i3][i4]=max(p,h);
                            }
                            else
                            {
                                if(fir==-1)fir=h;
                                h=0;
                            }
                        }
                        if(s[j]=='E')
                        {
                            if(i3==1)
                            {
                                h++;
                                ma[i1][i2][i3][i4]=max(p,h);
                            }
                            else
                            {
                                if(fir==-1)fir=h;
                                h=0;
                            }
                        }
                        if(s[j]=='N')
                        {
                            if(i4==1)
                            {
                                h++;
                                ma[i1][i2][i3][i4]=max(p,h);
                            }
                            else
                            {
                                if(fir==-1)fir=h;
                                h=0;
                            }
                        }
                        if(j==k-1&&h)
                        {
                            if(fir==-1)ma[i1][i2][i3][i4]=1000000000;
                            else ma[i1][i2][i3][i4]=max(ma[i1][i2][i3][i4],h+fir);
                        }
                    }
                    fir=-1;
                    h=0;
                }
            }
        }
    }
}
void check()
{
    for(int i1=0;i1<=1;i1++)
    {
        for(int i2=0;i2<=1;i2++)
        {
            for(int i3=0;i3<=1;i3++)
            {
                for(int i4=0;i4<=1;i4++)
                {
                    cout<<ma[i1][i2][i3][i4]<<" "<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<endl;
                }
            }
        }
    }
}
int bfs(cell beg)
{
    int br=1,w1,w2,w3,w4;
    cell w,nb;
    queue<cell>q;
    used[beg.a][beg.b]=1;
    q.push(beg);
    while(!q.empty())
    {
        w=q.front();
        q.pop();
        nb.a=w.a-1;
        nb.b=w.b;
        if(nb.a>0&&!used[nb.a][nb.b])
        {
            win[nb.a][nb.b][1]=1;
            w1=win[nb.a][nb.b][1];
            w2=win[nb.a][nb.b][2];
            w3=win[nb.a][nb.b][3];
            w4=win[nb.a][nb.b][4];
            if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
            {
                used[nb.a][nb.b]=1;
                br++;
                q.push(nb);
            }
        }
        nb.a=w.a;
        nb.b=w.b+1;
        if(nb.b<=m&&!used[nb.a][nb.b])
        {
            win[nb.a][nb.b][2]=1;
            w1=win[nb.a][nb.b][1];
            w2=win[nb.a][nb.b][2];
            w3=win[nb.a][nb.b][3];
            w4=win[nb.a][nb.b][4];
            if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
            {
                used[nb.a][nb.b]=1;
                br++;
                q.push(nb);
            }
        }
        nb.a=w.a;
        nb.b=w.b-1;
        if(nb.b>0&&!used[nb.a][nb.b])
        {
            win[nb.a][nb.b][3]=1;
            w1=win[nb.a][nb.b][1];
            w2=win[nb.a][nb.b][2];
            w3=win[nb.a][nb.b][3];
            w4=win[nb.a][nb.b][4];
            if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
            {
                used[nb.a][nb.b]=1;
                br++;
                q.push(nb);
            }
        }
        nb.a=w.a+1;
        nb.b=w.b;
        if(nb.a<=n&&!used[nb.a][nb.b])
        {
            win[nb.a][nb.b][4]=1;
            w1=win[nb.a][nb.b][1];
            w2=win[nb.a][nb.b][2];
            w3=win[nb.a][nb.b][3];
            w4=win[nb.a][nb.b][4];
            if(a[nb.a][nb.b]<=ma[w1][w2][w3][w4])
            {
                used[nb.a][nb.b]=1;
                br++;
                q.push(nb);
            }
        }
    }
    return br;
}
void read()
{
    cin>>k>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]==0)used[i][j]=1;
        }
    }
    prec();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!used[i][j])
            {
                cell d;
                d.a=i;
                d.b=j;
                int f=bfs(d);
                if(maa>f)
                {
                    maa=f;
                    otg=1;
                }
                else if(maa==f)
                {
                    otg++;
                }
                for(int i=1;i<=n;i++)
                {
                    for(int j=1;j<=m;j++)
                    {
                        if(a[i][j]!=0)used[i][j]=0;
                    }
                }
                memset(win,0,sizeof(win));
            }
        }
    }
    cout<<maa<<endl<<otg<<endl;
}
int main()
{
    speed();
    read();
    return 0;
}

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