Submission #1283483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283483		lechaa	Watching (JOI13_watching)	C++20	50 / 100	1098 ms	72236 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<int> dp(n+1, 2e9+2*n);
    dp[0] = 0;
    queue<pair<int, pair<int, int>>> q;
    queue<pair<int, pair<int, int>>> q1;
    for(int i = 0; i <= n; i++){
      vector<int> dp1(n+1, 2e9+2*n);
      while(q.size() > 0){
        pair<int, pair<int, int>> f = q.front();
        if(f.first < x[i]){
          q.pop();
          dp1[f.second.first] = min(f.second.second, dp1[f.second.first]);
        }else{
          break;
        }
      }
      while(q1.size() > 0){
        pair<int, pair<int, int>> f = q1.front();
        if(f.first < x[i]){
          q1.pop();
          dp1[f.second.first] = min(f.second.second, dp1[f.second.first]);
        }else{
          break;
        }
      }
      if(i > 0){
        swap(dp, dp1);
      }
      for(int y = 0; y <= n; y++){
        //1
        q.push({x[i] + mid-1, {y+1, dp[y]}});
        //2
        q1.push({x[i] + 2*mid-1, {y, dp[y]+1}});
      }
    }
    bool ns = false;
    for(int i = 0; i <= p; i++){
      if(dp[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: 0 / 50