Submission #443969

#TimeUsernameProblemLanguageResultExecution timeMemory
443969The_Panonian_SailorT-Covering (eJOI19_covering)C++14
0 / 100
3 ms332 KiB
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

bool sortpair(pair<int,int>a,pair<int,int>b)
{
    return (a.first<b.first && a.second<b.second);
}
int main()
{
    long n,m;
    int temp,k,sum=0;
    cin>>n>>m;
    vector<vector<int>> grid(n);
    bool a[n][m] {false};
    for (int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>temp;
            grid[i].push_back(temp);
        }
    }
    cin>>k;
    vector<pair<int,int>> spec(k);
    for(int i=0; i<k; i++)
    {
        cin>>spec[i].first>>spec[i].second;
        a[spec[i].first][spec[i].second]=true;
    }
    sort (spec.begin(), spec.end(), sortpair);
    int x1=-1,x2=-1, y1=-1,y2=-1, z1=-1,z2=-1 ,w1=-1,w2=-1;
    for(int i=0; i<k; i++)
    {
        x1=-1;x2=-1;y1=-1;y2=-1;z1=-1;z2=-1;w1=-1;w2=-1;
        if((spec[i].first>0 && spec[i].first<n-1 && spec[i].second>0 && spec[i].second<m-1)&&((a[spec[i].first][spec[i].second-1] && a[spec[i].first][spec[i].second+1])
           ||(a[spec[i].first+1][spec[i].second] && a[spec[i].first-1][spec[i].second])
           ||(a[spec[i].first+1][spec[i].second] && a[spec[i].first][spec[i].second+1])
           ||(a[spec[i].first+1][spec[i].second] && a[spec[i].first][spec[i].second-1])
           ||(a[spec[i].first][spec[i].second+1] && a[spec[i].first-1][spec[i].second])
           ||(a[spec[i].first][spec[i].second-1] && a[spec[i].first-1][spec[i].second])))
        {
            cout<<"No"<<endl;
            return 0;
        }
        else if((spec[i].first==0 && spec[i].second==0)
                || (spec[i].first==0 && spec[i].second==m-1)
                || (spec[i].first==n-1 && spec[i].second==0)
                || (spec[i].first==n-1 && spec[i].second==m-1))
        {
            cout<<"No"<<endl;
            return 0;
        }
        else if(spec[i].first==0)
        {
            sum+=grid[spec[i].first][spec[i].second];
            sum+=grid[spec[i].first][spec[i].second+1];
            a[spec[i].first][spec[i].second+1]=true;
            sum+=grid[spec[i].first][spec[i].second-1];
            a[spec[i].first][spec[i].second-1]=true;
            sum+=grid[spec[i].first+1][spec[i].second];
            a[spec[i].first+1][spec[i].second]=true;
        }
        else if(spec[i].first==n-1)
        {
            sum+=grid[spec[i].first][spec[i].second];
            sum+=grid[spec[i].first][spec[i].second+1];
            a[spec[i].first][spec[i].second+1]=true;
            sum+=grid[spec[i].first][spec[i].second-1];
            a[spec[i].first][spec[i].second-1]=true;
            sum+=grid[spec[i].first-1][spec[i].second];
            a[spec[i].first-1][spec[i].second]=true;
        }
        else if(spec[i].second==0)
        {
            sum+=grid[spec[i].first][spec[i].second];
            sum+=grid[spec[i].first+1][spec[i].second];
            a[spec[i].first+1][spec[i].second]=true;
            sum+=grid[spec[i].first-1][spec[i].second];
            a[spec[i].first-1][spec[i].second]=true;
            sum+=grid[spec[i].first][spec[i].second+1];
            a[spec[i].first][spec[i].second+1]=true;
        }
            else if(spec[i].second==m-1)
            {
                sum+=grid[spec[i].first][spec[i].second];
                sum+=grid[spec[i].first+1][spec[i].second];
                a[spec[i].first+1][spec[i].second]=true;
                sum+=grid[spec[i].first-1][spec[i].second];
                a[spec[i].first-1][spec[i].second]=true;
                sum+=grid[spec[i].first][spec[i].second-1];
                a[spec[i].first][spec[i].second-1]=true;
            }
            else if(a[spec[i].first+1][spec[i].second+1])
            {
                if(a[spec[i].first-1][spec[i].second]==false &&
                        a[spec[i].first+1][spec[i].second]==false &&
                        a[spec[i].first][spec[i].second+1]==false)
                {
                    a[spec[i].first-1][spec[i].second]=true;
                    a[spec[i].first+1][spec[i].second]=true;
                    a[spec[i].first][spec[i].second+1]=true;
                    sum+=grid[spec[i].first-1][spec[i].second]+grid[spec[i].first+1][spec[i].second]+grid[spec[i].first][spec[i].second+1];
                }
                else if(a[spec[i].first][spec[i].second+1]==false &&
                        a[spec[i].first][spec[i].second-1]==false &&
                        a[spec[i].first-1][spec[i].second]==false)
                {
                    a[spec[i].first][spec[i].second+1]=true;
                    a[spec[i].first][spec[i].second-1]=true;
                    a[spec[i].first-1][spec[i].second]=true;
                    sum+=grid[spec[i].first][spec[i].second+1]+grid[spec[i].first][spec[i].second-1]+grid[spec[i].first-1][spec[i].second];
                }
            }
            else
            {
                if(!a[spec[i].first-1][spec[i].second])
                {
                    x1=spec[i].first-1;
                    x2=spec[i].second;
                }
                if(!a[spec[i].first+1][spec[i].second])
                {
                    y1=spec[i].first+1;
                    y2=spec[i].second;
                }
                if(!a[spec[i].first][spec[i].second+1])
                {
                    z1=spec[i].first;
                    z2=spec[i].second+1;
                }
                if(!a[spec[i].first][spec[i].second-1])
                {
                    w1=spec[i].first;
                    w2=spec[i].second-1;
                }
                if(grid[x1][x2]<grid[y1][y2]){swap(x1,y1);swap(x2,y2);}
                if(grid[z1][z2]<grid[w1][w2]){swap(z1,w1);swap(z2,w2);}
                if(grid[x1][x2]<grid[w1][w2]){swap(x1,w1);swap(x2,w2);}
                if(grid[y1][y2]<grid[z1][z2]){swap(y1,z1);swap(y2,z2);}
                if(grid[x1][x2]<grid[y1][y2]){swap(x1,y1);swap(x2,y2);}
                if(grid[z1][z2]<grid[w1][w2]){swap(z1,w1);swap(z2,w2);}
                sum+=grid[x1][x2]+grid[y1][y2]+grid[z1][z2];
                a[x1][x2]=true;
                a[y1][y2]=true;
                a[z1][z2]=true;
            }
        }
        cout<<sum<<endl;
        return 0;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...