제출 #413881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413881		600Mihnea	Cultivation (JOI17_cultivation)	C++17	5 / 100	2098 ms	262148 KiB

cultivation

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, cnt;

bool valid(pair<int, int> a) {
  return 1 <= a.first && a.first <= n && 1 <= a.second && a.second <= m;
}



set<pair<int, int>> get(set<pair<int, int>> a, int dx, int dy) {
  set<pair<int, int>> sol = a;
  for (auto &it : a) {
    sol.insert({it.first + dx, it.second + dy});
  }
  for (auto &it : sol) {
    if (valid(it)) {
      a.insert(it);
    }
  }
  return a;
}

int bkt(set<pair<int, int>> s) {
  if ((int) s.size() == n * m) return 0;

  int cnt = 0;
  vector<set<pair<int, int>>> all;
  for (int dx = -1; dx <= +1; dx++) {
    for (int dy = -1; dy <= +1; dy++) {
      if (abs(dx) + abs(dy) != 1) continue;
      cnt++;
      set<pair<int, int>> s2 = get(s, dx, dy);
      ///cout << " : " << (int) s.size() << " and " << (int) s2.size() << "\n";
      if ((int) s2.size() > (int) s.size()) {
        all.push_back(s2);
      }
    }
  }
  assert(cnt == 4);


  assert(!all.empty());

  int best = (int) 1e9;

  for (auto &s2 : all) {
    best = min(best, bkt(s2) + 1);
  }

  return best;
}


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  cin >> n >> m >> cnt;
  set<pair<int, int>> s;

  for (int i = 1; i <= cnt; i++) {
    int x, y;
    cin >> x >> y;
    s.insert({x, y});
  }

  cout << bkt(s) << "\n";

  return 0;
}

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