Submission #466212

#	Time	Username	Problem	Language	Result	Execution time	Memory
466212		Tenis0206	T-Covering (eJOI19_covering)	C++11	25 / 100	280 ms	11720 KiB

covering

#include <bits/stdc++.h>

using namespace std;
int dx[] = {0,0,1,-1,1,-1,1,-1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
vector<pair<int,int>> grupa;
vector<vector<pair<int,int>>> gr;
int n,m,k,a[1005][1005],sp[1005][1005];
bool sel[1005][1005];
void Fill(int x, int y)
{
    grupa.push_back({x,y});
    sp[x][y] = false;
    for(int p=0;p<8;p++)
    {
        int xx = x + dx[p];
        int yy = y + dy[p];
        if(sp[xx][yy])
        {
            Fill(xx,yy);
        }
    }
}
void bordare()
{
    for(int i=0;i<=n+1;i++)
    {
        sel[i][0] = sel[i][m+1] = true;
    }
    for(int i=0;i<=m+1;i++)
    {
        sel[0][i] = sel[n+1][i] = true;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    bordare();
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        ++x;
        ++y;
        sp[x][y] = true;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!sp[i][j])
            {
                continue;
            }
            grupa.clear();
            Fill(i,j);
            if(grupa.size()>2)
            {
                cout<<"No"<<'\n';
                return 0;
            }
            gr.push_back(grupa);
        }
    }
    long long sum = 0;
    for(auto v : gr)
    {
        if(v.size()==1)
        {
            continue;
        }
        pair<int,int> x = v[0];
        pair<int,int> y = v[1];
        if(x.first==y.first)
        {
            if(x.second>y.second)
            {
                swap(x,y);
            }
            int i = x.first;
            int j = x.second;
            if(sel[i][j] || sel[i][j-1] || sel[i-1][j] || sel[i+1][j] || sel[i][j+1] || sel[i][j+2] || sel[i-1][j+1] || sel[i+1][j+1])
            {
                cout<<"No"<<'\n';
                return 0;
            }
            sum += (a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+1] + a[i+1][j+1]);
            sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = sel[i][j+1] = sel[i][j+2] = sel[i-1][j+1] = sel[i+1][j+1] = true;
        }
        else if(x.second==y.second)
        {
            if(x.first>y.first)
            {
                swap(x,y);
            }
            int i = x.first;
            int j = x.second;
            if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j] || sel[i+2][j] || sel[i+1][j-1] || sel[i+1][j+1])
            {
                cout<<"No"<<'\n';
                return 0;
            }
            sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j] + a[i+2][j] + a[i+1][j-1] + a[i+1][j+1]);
            sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j] = sel[i+2][j] = sel[i+1][j-1] = sel[i+1][j+1] = true;
        }
        else if((x.first<y.first && x.second<y.second) || (x.first>y.first && x.second>y.second))
        {
            if(x.first>y.first)
            {
                swap(x,y);
            }
            int i = x.first;
            int j = x.second;
            if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j+1] || sel[i+2][j+1] || sel[i+1][j] || sel[i+1][j+2])
            {
                cout<<"No"<<'\n';
                return 0;
            }
            sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1] + a[i+1][j] + a[i+1][j+2]);
            sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j+1] = sel[i+2][j+1] = sel[i+1][j] = sel[i+1][j+2] = true;
        }
        else
        {
            if(x.first>y.first)
            {
                swap(x,y);
            }
            int i = x.first;
            int j = x.second;
            if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j-1] || sel[i+2][j-1] || sel[i+1][j-2] || sel[i+1][j])
            {
                cout<<"No"<<'\n';
                return 0;
            }
            sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j-1] + a[i+2][j-1] + a[i+1][j-2] + a[i+1][j]);
            sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j-1] = sel[i+2][j-1] = sel[i+1][j-2] = sel[i+1][j] = true;
        }
    }
    for(auto v : gr)
    {
        if(v.size()==2)
        {
            continue;
        }
        int i = v[0].first;
        int j = v[0].second;
        int Max = 0;
        if(!sel[i][j] && !sel[i+1][j] && !sel[i][j-1] && !sel[i][j+1])
        {
            Max = max(Max,a[i][j] + a[i+1][j] + a[i][j-1] + a[i][j+1]);
        }
        if(!sel[i][j] && !sel[i-1][j] && !sel[i][j-1] && !sel[i][j+1])
        {
            Max = max(Max,a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1]);
        }
        if(!sel[i][j] && !sel[i][j+1] && !sel[i-1][j] && !sel[i+1][j])
        {
            Max = max(Max,a[i][j] + a[i][j+1] + a[i-1][j] + a[i+1][j]);
        }
        if(!sel[i][j] && !sel[i][j-1] && !sel[i-1][j] && !sel[i+1][j])
        {
            Max = max(Max,a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j]);
        }
        if(!Max)
        {
            cout<<"No"<<'\n';
            return 0;
        }
        if(Max==a[i][j]+a[i+1][j]+a[i][j-1]+a[i][j+1])
        {
            sel[i][j] = sel[i+1][j] = sel[i][j-1] = sel[i][j+1] = true;
        }
        else if(Max==a[i][j]+a[i-1][j]+a[i][j-1]+a[i][j+1])
        {
            sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = true;
        }
        else if(Max==a[i][j]+a[i][j+1]+a[i-1][j]+a[i+1][j])
        {
            sel[i][j] = sel[i][j+1] = sel[i-1][j] = sel[i+1][j] = true;
        }
        else if(Max==a[i][j]+a[i][j-1]+a[i-1][j]+a[i+1][j])
        {
            sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = true;
        }
        sum+=Max;
    }
    cout<<sum<<'\n';
    return 0;
}

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