Submission #641730

#	Time	Username	Problem	Language	Result	Execution time	Memory
641730		Urvuk3	T-Covering (eJOI19_covering)	C++17	15 / 100	1093 ms	340 KiB

covering

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(niz) { cerr<<#niz<<"="; for(auto _i:niz) cerr<<_i<<" "; cerr<<endl; }
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

void Solve(){
    int N,M; cin>>N>>M;
    vector<vector<int>> a(N+1,vector<int>(M+1,0));
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin>>a[i][j];
        }
    }
    int K; cin>>K;
    vector<pii> spec(K+1);
    for(int i=1;i<=K;i++){
        cin>>spec[i].fi>>spec[i].se;
        spec[i].fi++;
        spec[i].se++;
    }
    bool subtask4=(K<=10);
    function<bool(int,int)> Valid=[&](int i,int j){
        return (1<=i && i<=N) && (1<=j && j<=M);
    };
    if(subtask4){
        vector<int> vec={0};
        int res=-1;
        function<void(int,vector<int>)> Gen=[&](int id,vector<int> v){
            if(id==K+1){
                vector<vector<bool>> ocupied(N+1,vector<bool>(M+1,false));
                bool ok=true;
                bool razmatram=(v==vector<int>({0,1,3,0}));
                for(int idx=1;idx<=K;idx++){
                    int i=spec[idx].fi,j=spec[idx].se;
                    ok&=!ocupied[i][j];
                    ocupied[i][j]=1;
                    if(v[idx]==0){
                        ok&=!ocupied[i][j+1] & !ocupied[i][j-1] & !ocupied[i-1][j];
                        ocupied[i][j+1]=1; ocupied[i][j-1]=1; ocupied[i-1][j]=1;
                    }
                    else if(v[idx]==1){
                        ok&=!ocupied[i][j-1] & !ocupied[i-1][j] & !ocupied[i+1][j];
                        ocupied[i][j-1]=1; ocupied[i-1][j]=1; ocupied[i+1][j]=1;
                    }
                    else if(v[idx]==2){
                        ok&=!ocupied[i][j+1] & !ocupied[i][j-1] & !ocupied[i+1][j];
                        ocupied[i][j+1]=1; ocupied[i][j-1]=1; ocupied[i+1][j]=1;
                    }
                    else{
                        ok&=!ocupied[i][j+1] & !ocupied[i-1][j] & !ocupied[i+1][j];
                        ocupied[i][j+1]=1; ocupied[i-1][j]=1; ocupied[i+1][j]=1;
                    }
                }
                int ret=0;
                for(int i=1;i<=N;i++){
                    for(int j=1;j<=M;j++){
                        ret+=(ocupied[i][j] ? a[i][j] : 0);
                    }
                }
                if(ok) res=max(res,ret);
                return;
            }
            else{
                int i=spec[id].fi,j=spec[id].se;
                v.pb(0);
                if(Valid(i,j+1) && Valid(i,j-1) && Valid(i-1,j)){
                    Gen(id+1,v);
                } v.pop_back();
                v.pb(1);
                if(Valid(i,j-1) && Valid(i-1,j) && Valid(i+1,j)){
                    Gen(id+1,v);
                } v.pop_back();
                v.pb(2);
                if(Valid(i,j+1) && Valid(i,j-1) && Valid(i+1,j)){
                    Gen(id+1,v);
                } v.pop_back();
                v.pb(3);
                if(Valid(i,j+1) && Valid(i-1,j) && Valid(i+1,j)){
                    Gen(id+1,v);
                } v.pop_back();
            }
        }; Gen(1,vec);
        cout<<(res!=-1 ? to_string(res) : "No" )<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

Compilation message (stderr)

covering.cpp: In lambda function:
covering.cpp:47:22: warning: unused variable 'razmatram' [-Wunused-variable]
   47 |                 bool razmatram=(v==vector<int>({0,1,3,0}));
      |                      ^~~~~~~~~

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