제출 #1131030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131030		Hamed_Ghaffari	Watching (JOI13_watching)	C++20	100 / 100	192 ms	16144 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

using pii = pair<int, int>;

#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 2e3+5;

int n, P, Q, a[MXN], dp[MXN][MXN];

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> P >> Q; P = min(P, n); Q = min(Q, n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a, a+n);
  auto check = [&](int w) {
    int lw=-1, l2w=-1;
    for(int i=0; i<n; i++) {
      while(a[i]-a[lw+1]+1>w) lw++;
      while(a[i]-a[l2w+1]+1>w+w) l2w++;
      for(int j=0; j<=P; j++) {
        dp[i][j] = j ? (lw==-1 ? 0  : dp[lw][j-1]) : 1e9;
        dp[i][j] = min(dp[i][j], (l2w==-1 ? 0 : dp[l2w][j]) + 1);
      }
    }
    return *min_element(dp[n-1], dp[n-1]+P+1) <= Q;
  };
  int l=0, r=1e9;
  while(r-l>1)
    (check(l+r>>1) ? r : l) = l+r>>1;
  cout << r << '\n';
  return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50