Submission #1221638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221638		mayac	T-Covering (eJOI19_covering)	C++20	0 / 100	167 ms	504 KiB

covering

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll=long long;

int main(){
    int n,m,ans=0,k,a,b,cur;
    cin>>n>>m;
    vector<vector<int>> v(n+2,vector<int>(m+2,-1)),d(n+2,vector<int>(m+2,-1));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i+1][j+1];
            d[i+1][j+1]=v[i+1][j+1];
        }
    }
    cin>>k;
    bool flag=0,tmp;
    vector<pair<int,int>> p(k);
    for(int i=0;i<k;i++){
        cin>>a>>b;
        p[i]={a+1,b+1};
    }
    for(int t=0;t<(1<<(2*k));t++){
        tmp=1;
        cur=0;
        for(int i=0;i<k;i++){
            a=p[i].first;b=p[i].second;
            if((t&(1<<(2*i)))&&(t&(1<<(2*i+1)))){
                if(d[a][b]==-1||d[a-1][b]==-1||d[a][b+1]==-1||d[a][b-1]==-1)tmp=0;
                cur+=d[a][b]+d[a-1][b]+d[a][b+1]+d[a][b-1];
                d[a][b]=-1;d[a-1][b]=-1;d[a][b+1]=-1;d[a][b-1]=-1;
            }
            if((t&(1<<(2*i)))&&!(t&(1<<(2*i+1)))){
                if(d[a][b]==-1||d[a+1][b]==-1||d[a][b+1]==-1||d[a][b-1]==-1)tmp=0;
                cur+=d[a][b]+d[a+1][b]+d[a][b+1]+d[a][b-1];
                d[a][b]=-1;d[a+1][b]=-1;d[a][b+1]=-1;d[a][b-1]=-1;
            }
            if(!(t&(1<<(2*i)))&&(t&(1<<(2*i+1)))){
                if(d[a][b]==-1||d[a-1][b]==-1||d[a+1][b]==-1||d[a][b-1]==-1)tmp=0;
                cur+=d[a][b]+d[a-1][b]+d[a+1][1]+d[a][b-1];
                d[a][b]=-1;d[a-1][b]=-1;d[a+1][b]=-1;d[a][b-1]=-1;
            }
            if(!(t&(1<<(2*i)))&&!(t&(1<<(2*i+1)))){
                if(d[a][b]==-1||d[a-1][b]==-1||d[a+1][b]==-1||d[a][b+1]==-1)tmp=0;
                cur+=d[a][b]+d[a-1][b]+d[a+1][1]+d[a][b-1];
                d[a][b]=-1;d[a-1][b]=-1;d[a+1][b]=-1;d[a][b+1]=-1;
            }
        }
        for(int i=0;i<k;i++){
            a=p[i].first;b=p[i].second;
            if((t&(1<<(2*i)))&&(t&(1<<(2*i+1)))){
                d[a][b]=v[a][b];d[a-1][b]=v[a-1][b];d[a][b+1]=v[a][b+1];d[a][b-1]=v[a][b-1];
            }
            if((t&(1<<(2*i)))&&!(t&(1<<(2*i+1)))){
                d[a][b]=v[a][b];d[a+1][b]=v[a+1][b];d[a][b+1]=v[a][b+1];d[a][b-1]=v[a][b-1];
            }
            if(!(t&(1<<(2*i)))&&(t&(1<<(2*i+1)))){
                d[a][b]=v[a][b];d[a-1][b]=v[a-1][b];d[a+1][b]=v[a+1][b];d[a][b-1]=v[a][b-1];
            }
            if(!(t&(1<<(2*i)))&&(t&(1<<(2*i+1)))){
                d[a][b]=v[a][b];d[a-1][b]=v[a-1][b];d[a-1][b]=v[a-1][b];d[a][b-1]=v[a][b-1];
            }
        }
        if(tmp){
            //cout<<cur<<"\n";
            flag=1;
            ans=max(ans,cur);
        }
    }
    if(flag)cout<<ans<<"\n";
    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