Submission #443975

#TimeUsernameProblemLanguageResultExecution timeMemory
443975The_Panonian_SailorT-Covering (eJOI19_covering)C++14
0 / 100
4 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};
    int r[4];
    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);
    for(int i=0; i<k; i++)
    {
        sum+=grid[spec[i].first][spec[i].second];
        if((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][spec[i].second+1]))
        {
            cout<<"No"<<endl;
            return 0;
        }
        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
        {
             r[0]=0;r[1]=0;r[2]=0;r[3]=0;
            if(spec[i].first<n-1 && !a[spec[i].first+1][spec[i].second])
            {
            r[0]=grid[spec[i].first+1][spec[i].second];
            a[spec[i].first+1][spec[i].second]=true;
            }
            if(spec[i].first>0 &&!a[spec[i].first-1][spec[i].second])
            {
            r[1]=grid[spec[i].first-1][spec[i].second];
            a[spec[i].first-1][spec[i].second]=true;
            }
            if(spec[i].second<m-1 && !a[spec[i].first][spec[i].second+1])
            {
            r[2]=grid[spec[i].first][spec[i].second+1];
            a[spec[i].first][spec[i].second+1]=true;
            }
            if(spec[i].second>0 && !a[spec[i].first][spec[i].second-1])
            {
            r[3]=grid[spec[i].first][spec[i].second-1];
            a[spec[i].first][spec[i].second-1]=true;
            }
            sort(r,r+4);
            sum+=r[3]+r[2]+r[1];
            cout<<sum<<endl;
            if(r[0]==0 &&r[1]==0)
            {
                cout<<"No"<<endl;
                return 0;
            }
            if (grid[spec[i].first+1][spec[i].second]==r[0])
            {
                a[spec[i].first+1][spec[i].second]=false;
            }
            else if(grid[spec[i].first-1][spec[i].second]==r[0])
            {
                a[spec[i].first-1][spec[i].second]=false;
            }
            else if(r[0]==grid[spec[i].first][spec[i].second+1])
            {
                a[spec[i].first][spec[i].second+1]=false;
            }
            else if(r[0]==grid[spec[i].first][spec[i].second-1])
            {
                a[spec[i].first][spec[i].second-1]=false;
            }
        }
    }
    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...