Submission #577249

#	Time	Username	Problem	Language	Result	Execution time	Memory
577249		berr	T-Covering (eJOI19_covering)	C++17	0 / 100	122 ms	388 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin>>n>>m;
    int val[n][m];
    bool check[n][m];

    for(int i=0; i<n; i++)
    {
        for(int l=0; l<m; l++)
            cin>>val[i][l];
    }

    int k; cin>>k;

    vector<vector<int>> groups;
    vector<array<int, 2>> ind(k);

    for(int i=0; i<k; i++)
    {
        cin>>ind[i][0]>>ind[i][1];
    }

    n--;

    int ans=0,  daa=0;
    m--;

    for(int i=0; i<(1<<(2*k)); i++)
    {   

        int s=0;
        int f=0;
        for(int l=2*k, t=0; l>1; l-=2, t++)
        {
            int x=ind[t][0];
            int y=ind[t][1];
            if(i&(1LL<<l))
            {

                if(i&(1LL<<(l-1)))
                {
                    if(x>=1&&x<=n-1&&y>=1)
                    {
                        if(check[x][y]!=i&&check[x-1][y]!=i&&check[x+1][y]!=i&&check[x][y-1]!=i)
                            s+=val[x][y]+val[x-1][y]+val[x+1][y]+val[x][y-1];
                        else
                            f=1;
                        check[x][y]=check[x-1][y]=check[x+1][y]=check[x][y-1]=i;
                    }
                    else f=1;
                }

                else
                {
                    if(x>=1&&x<=n-1&&y<=m-1)
                    {
                        if(check[x][y]!=i&&check[x-1][y]!=i&&check[x+1][y]!=i&&check[x][y+1]!=i)
                            s+=val[x][y]+val[x-1][y]+val[x+1][y]+val[x][y+1];
                        else
                            f=1;
                        check[x][y]=check[x-1][y]=check[x+1][y]=check[x][y+1]=i;
                    }
                    else
                        f=1;
                }
            }
            else
            {
                if(i&(1LL<<(l+1)))
                {
                    if(y>=1&&y<=m-1&&x>=1)
                    {
                        if(check[x][y]!=i&&check[x][y-1]!=i&&check[x][y+1]!=i&&check[x-1][y]!=i)
                            s+=val[x][y]+val[x][y-1]+val[x][y+1]+val[x-1][y];
                        else
                            f=1;
                        check[x][y]=check[x][y-1]=check[x][y+1]=check[x-1][y]=i;
                    }
                    else f=1;
                }

                else
                {
                    if(y>=1&&y<=m-1&&x<=n-1)
                    {
                        if(check[x][y]!=i&&check[x][y-1]!=i&&check[x][y+1]!=i&&check[x+1][y]!=i)
                            s+=val[x][y]+val[x][y-1]+val[x][y+1]+val[x+1][y];
                        else
                            f=1;
                        check[x][y]=check[x][y-1]=check[x][y+1]=check[x+1][y]=i;
                    }
                    else f=1;
                }
            } 
        }



        if(f==0) ans=max(ans, s), daa=1;
    }

    if(daa) cout<<ans;
    else cout<<"NO\n";







}

• Subtask 1: 0 / 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