Submission #5374977

---

Source Code Expand

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

#define int long long

int N, K;
vector<int> a, v;

bool check(int mid) {
  int cnt = 0;
  mid++;
  for (int i = 0; i < N; i++) {
    if (v[i] % mid == 0) {
      cnt++;
    }
  }

  return cnt <= K;
}

// 二分探索
int bin() {
  int ok = N + 10;
  int ng = 0; // -1だとcheck()関数で受け切れないので死ぬ
  while (ok - ng > 1) {
    int mid = (ok + ng) / 2;
    if (check(mid)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }

  return ok;
}

signed main() {
  cin >> N >> K;
  a.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }

  // 何個連続してるかっていう配列を作る
  int old = a[0];
  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a[i] == old) {
      cnt++;
    } else {
      old = a[i];
      cnt = 1;
    }
    v.push_back(cnt);
  }

  int ans = bin();

  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result