Submission #752714

#	Time	Username	Problem	Language	Result	Execution time	Memory
752714		MateiKing80	T-Covering (eJOI19_covering)	C++14	5 / 100	207 ms	6096 KiB

covering

#include <iostream>

using namespace std;

int m,n;

int fct(int x, int y)
{
    x--;
    y--;
    return m*x+y;
}

int v[1000005];
bool f[1000005];
bool oc[1000005];

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>v[fct(i,j)];
    int k;
    cin>>k;
    for(int i=0; i<k; i++)
    {
        int a,b;
        cin>>a>>b;
        a++;
        b++;
        f[fct(a,b)]=true;
    }
    long long ans=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(f[fct(i,j)]==true)
            {
                if(j<m && f[fct(i,j+1)]==true)
                {
                    if(j==1 || j==m-1 || i==1 || i==n || oc[fct(i,j)] ||oc[fct(i,j+1)] ||oc[fct(i,j+2)] ||oc[fct(i,j-1)] ||oc[fct(i-1,j)] ||oc[fct(i+1,j)] ||oc[fct(i-1,j+1)] ||oc[fct(i+1,j+1)])
                    {
                        cout<<"No";
                        return 0;
                    }
                    f[fct(i,j+1)] = false;
                    oc[fct(i,j)]=true;
                    oc[fct(i,j+1)] =true;
                    oc[fct(i,j+2)]=true;
                    oc[fct(i,j-1)]=true;
                    oc[fct(i-1,j)] =true;
                    oc[fct(i+1,j)] =true;
                    oc[fct(i-1,j+1)]=true;
                    oc[fct(i+1,j+1)]=true;
                }
                else if(i<n && f[fct(i+1,j)]==true)
                {
                    if(j==1 || j==m || i==1 || i==n-1 || oc[fct(i,j)] || oc[fct(i,j+1)] || oc[fct(i-1,j)] || oc[fct(i,j-1)] || oc[fct(i+1,j)] || oc[fct(i+1,j-1)]  || oc[fct(i+1,j+1)] || oc[fct(i+1,j)])
                    {
                        cout<<"Nosus";
                        return 0;
                    }
                    f[fct(i+1,j)]=false;
                    oc[fct(i,j)]=true;
                    oc[fct(i,j+1)]=true;
                    oc[fct(i-1,j)]=true;
                    oc[fct(i,j-1)]=true;
                    oc[fct(i+1,j)]=true;
                    oc[fct(i+1,j-1)]=true;
                    oc[fct(i+1,j+1)]=true;
                    oc[fct(i+1,j)]=true;
                }
                else
                {
                    if(i==1 || oc[fct(i-1,j)])
                    {
                        if(j==1 || j==m || oc[fct(i,j)] || oc[fct(i,j+1)] || oc[fct(i,j-1)] || oc[fct(i+1,j)])
                        {
                            cout<<"No";
                            return 0;
                        }
                        oc[fct(i,j)]=true;
                        oc[fct(i,j+1)]=true;
                        oc[fct(i,j-1)]=true;
                        oc[fct(i+1,j)]=true;
                    }
                    else if(i==n || oc[fct(i+1,j)])
                    {
                        if(j==1 || j==m || oc[fct(i,j)] || oc[fct(i,j+1)] || oc[fct(i,j-1)] || oc[fct(i-1,j)])
                        {
                            cout<<"No";
                            return 0;
                        }
                        oc[fct(i,j)]=true;
                        oc[fct(i,j+1)]=true;
                        oc[fct(i,j-1)]=true;
                        oc[fct(i-1,j)]=true;
                    }
                    else if(j==1 || oc[fct(i,j-1)])
                    {
                        if(i==1 || i==n || oc[fct(i,j)] || oc[fct(i+1,j)] || oc[fct(i-1,j)] || oc[fct(i,j+1)])
                        {
                            cout<<"No";
                            return 0;
                        }
                        oc[fct(i,j)]=true;
                        oc[fct(i+1,j)]=true;
                        oc[fct(i-1,j)]=true;
                        oc[fct(i,j+1)]=true;
                    }
                    else if(j==m || oc[fct(i,j+1)])
                    {
                        if(i==1 || i==n || oc[fct(i,j)] || oc[fct(i+1,j)] || oc[fct(i-1,j)] || oc[fct(i,j-1)])
                        {
                            cout<<"No";
                            return 0;
                        }
                        oc[fct(i,j)]=true;
                        oc[fct(i+1,j)]=true;
                        oc[fct(i-1,j)]=true;
                        oc[fct(i,j-1)]=true;
                    }
                    else
                    {
                        int minn=min(v[fct(i,j-1)],min(v[fct(i,j+1)], min(v[fct(i-1,j)],v[fct(i+1,j)])));
                        if(minn==v[fct(i-1,j)])
                        {
                            oc[fct(i,j)]=true;
                            oc[fct(i,j+1)]=true;
                            oc[fct(i,j-1)]=true;
                            oc[fct(i+1,j)]=true;
                        }
                        else if(minn==v[fct(i+1,j)])
                        {

                            oc[fct(i,j)]=true;
                            oc[fct(i,j+1)]=true;
                            oc[fct(i,j-1)]=true;
                            oc[fct(i-1,j)]=true;
                        }
                        else if(minn==v[fct(i,j-1)])
                        {

                            oc[fct(i,j)]=true;
                            oc[fct(i+1,j)]=true;
                            oc[fct(i-1,j)]=true;
                            oc[fct(i,j+1)]=true;
                        }
                        else
                        {

                            oc[fct(i,j)]=true;
                            oc[fct(i+1,j)]=true;
                            oc[fct(i-1,j)]=true;
                            oc[fct(i,j-1)]=true;
                        }
                    }
                }
            }
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(oc[fct(i,j)])
                ans+=v[fct(i,j)];
    cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30