Submission #256166

#	Time	Username	Problem	Language	Result	Execution time	Memory
256166		jdh	T-Covering (eJOI19_covering)	C++17	0 / 100	1 ms	512 KiB

covering

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
ll n,m;
ll check(ll x1,ll y1,vector<vector<bool>>& cen,vector<vector<ll>>& a){
  multiset<ll> cands,noncands;
  ll ret = 0,nbc = 1,nb = 0;
  deque<pair<ll,ll>> q;
  q.emplace_back(x1,y1);
  vector<vector<bool>> done(m,vector<bool>(n));
  while(!q.empty()){
    ll x,y;
    tie(x,y) = q.front();
    q.pop_front();
    ++nbc;
    if(a[x][y] < 0) return -inf;
    a[x][y] = -inf;
    for(ll i = max(0ll,x-1); i <= min(m-1,x+1); ++i){
      for(ll j = max(0ll,y-1); j <= min(n-1,y+1); ++j){
        if(a[i][j] >= 0){
          cands.emplace(a[i][j]);
          ret += a[i][j];
          a[i][j] = -inf;
          ++nb;
        }
      }
    }
    if(x >= 2 and cen[x-2][y]){
      if(a[x-1][y] >= 0) noncands.emplace(a[x-1][y]);
      if(!done[x-2][y]){
        done[x-2][y] = true;
        q.emplace_back(x-2,y);
      }
    }
    if(x < m-2 and cen[x+2][y]){
      if(a[x+1][y] >= 0) noncands.emplace(a[x+1][y]);
      if(!done[x+2][y]){
        done[x+2][y] = true;
        q.emplace_back(x+2,y);
      }
    }
    if(y >= 2 and cen[x][y-2]){
      if(a[x][y-1] >= 0) noncands.emplace(a[x][y-1]);
      if(!done[x][y-2]){
        done[x][y-2] = true;
        q.emplace_back(x,y-2);
      }
    }
    if(y < n-2 and cen[x][y+2]){
      if(a[x][y+1] >= 0) noncands.emplace(a[x][y+1]);
      if(!done[x][y+2]){
        done[x][y+2] = true;
        q.emplace_back(x,y+2);
      }
    }
  }
  if(nb < 3*nbc) return -inf;
  if(nb == 3*nbc) return ret;
  if(nb > 3*nbc+1) return -inf;
  for(ll i : noncands) cands.erase(cands.find(i));
  ret -= *begin(cands);
  return ret;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll k,x,y;
  cin >> m >> n;
  vector<vector<ll>> a(m,vector<ll>(n));
  for(ll i = 0; i < m; ++i){
    for(ll j = 0; j < n; ++j) cin >> a[i][j];
  }
  vector<vector<bool>> cen(m,vector<bool>(n));
  cin >> k;
  vector<pair<ll,ll>> vp;
  for(ll i = 0; i < k; ++i){
    cin >> x >> y;
    cen[x][y] = true;
    vp.emplace_back(x,y);
  }
  for(auto& p : vp){
    tie(x,y) = p;
    ll cnt = 0,tot = 0;
    for(ll i = max(0ll,x-1); i <= min(m-1,x+1); ++i){
      for(ll j = max(0ll,y-1); j <= min(n-1,y+1); ++j){
        if(cen[i][j]) ++cnt;
        ++tot;
      }
    }
    if(cnt >= 3 or (tot <= 6 and cnt >= 2) or tot <= 4){
      cout << "No";
      return 0;
    }
  }
  ll ans = 0;
  vector<pair<ll,ll>> vp2;
  for(auto& p : vp){
    tie(x,y) = p;
    if(0 < x and x < m-1 and 0 < y and y < n-1){
      if(cen[x-1][y-1] or cen[x-1][y] or cen[x-1][y+1]){
        if(a[x][y-1] < 0 or a[x][y] < 0 or a[x][y+1] < 0 or a[x+1][y] < 0){
          cout << "No";
          return 0;
        }
        ans += a[x][y-1]+a[x][y+1]+a[x+1][y];
        a[x][y-1] = a[x][y] = a[x][y+1] = a[x+1][y] = -inf;
      }
      else if(cen[x+1][y-1] or cen[x+1][y] or cen[x+1][y+1]){
        if(a[x][y-1] < 0 or a[x][y] < 0 or a[x][y+1] < 0 or a[x-1][y] < 0){
          cout << "No";
          return 0;
        }
        ans += a[x][y-1]+a[x][y+1]+a[x-1][y];
        a[x][y-1] = a[x][y] = a[x][y+1] = a[x-1][y] = -inf;
      }
      else if(cen[x][y-1]){
        if(a[x-1][y] < 0 or a[x][y] < 0 or a[x+1][y] < 0 or a[x][y+1] < 0){
          cout << "No";
          return 0;
        }
        ans += a[x-1][y]+a[x+1][y]+a[x][y+1];
        a[x-1][y] = a[x][y] = a[x+1][y] = a[x][y+1] = -inf;
      }
      else if(cen[x][y+1]){
        if(a[x-1][y] < 0 or a[x][y] < 0 or a[x+1][y] < 0 or a[x][y-1] < 0){
          cout << "No";
          return 0;
        }
        ans += a[x-1][y]+a[x+1][y]+a[x][y-1];
        a[x-1][y] = a[x][y] = a[x+1][y] = a[x][y-1] = -inf;
      }
      else vp2.emplace_back(x,y);
    }
    else{
      if(a[x][y] < 0){
        cout << "No";
        return 0;
      }
      a[x][y] = -inf;
      int nb = 0;
      if(x > 0 and a[x-1][y] >= 0){
        ans += a[x-1][y];
        a[x-1][y] = -inf;
        ++nb;
      }
      if(x < m-1 and a[x+1][y] >= 0){
        ans += a[x+1][y];
        a[x+1][y] = -inf;
        ++nb;
      }
      if(y > 0 and a[x][y-1] >= 0){
        ans += a[x][y-1];
        a[x][y-1] = -inf;
        ++nb;
      }
      if(y < n-1 and a[x][y+1] >= 0){
        ans += a[x][y+1];
        a[x][y+1] = -inf;
        ++nb;
      }
      if(nb != 3){
        cout << "No";
        return 0;
      }
    }
  }
  vector<vector<bool>> cen2(m,vector<bool>(n));
  for(auto& p : vp2){
    tie(x,y) = p;
    cen2[x][y] = true;
  }
  for(auto& p : vp2){
    tie(x,y) = p;
    if(a[x][y] >= 0){
      ll tmp = check(x,y,cen2,a);
      if(tmp < 0){
        cout << "No";
        return 0;
      }
      ans += tmp;
    }
  }
  cout << ans;
  return 0;
}

• 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