Submission #1283496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283496		lechaa	Watching (JOI13_watching)	C++20	100 / 100	341 ms	16284 KiB

watching

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

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, p, lim; cin >> n >> p >> lim;
  vector<int> x(n);
  for(int i = 0; i < n; i++){
    cin >> x[i];
  }
  x.push_back(2e9+2*n);
  sort(x.begin(), x.end());
  p = min(p, n);
  lim = min(lim, n);
  int low = 1;
  int top = 1e9;
  int ans = 0;
  while(low <= top){
    int mid = (low + top)/2;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 2e9+2*n));
    dp[0][0] = 0;
    int q = 0;
    int q1 = 0;
    for(int i = 0; i <= n; i++){
      if(i > 0){
        while(x[i] - x[q] + 1 > mid){
          for(int y = 0; y <= p; y++){
            dp[i][y+1] = min(dp[i][y+1], dp[q][y]);
          }
          q++;
        }
        while(x[i] - x[q1] + 1 > 2*mid){
          for(int y = 0; y <= p; y++){
            dp[i][y] = min(dp[i][y], dp[q1][y]+1);
          }
          q1++;
        }
      }
    }
    bool ns = false;
    for(int i = 0; i <= p; i++){
      if(dp[n][i] <= lim){
        ns = true;
      }
    }
    if(ns){
      top = mid-1;
      ans = mid;
    }else{
      low = mid+1;
    }
  }
  cout << ans << "\n";
  return 0;
}

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