Submission #373455

#	Time	Username	Problem	Language	Result	Execution time	Memory
373455		Halit	Watching (JOI13_watching)	C++17	100 / 100	669 ms	16544 KiB

watching

//author: Halit
#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <climits>

int main() {
  int64_t n, p, q;
  std::cin >> n >> p >> q;

  std::vector<int64_t> a(n);
  for (int64_t &el : a) {
    std::cin >> el;
  } std::sort(a.begin(), a.end());

  int64_t l = 0, r = INT_MAX;
  while (l < r) {
    int64_t w = (l+r)/2;
    std::vector<int64_t> size = {w-1, w*2-1};

    std::vector< std::vector<int> > next(2, std::vector<int>(n));
    for (int t = 0; t < 2; ++t) {
      for (int i = 0, j = 0;i < n; ++i) {
        while (j < n && a[j] <= a[i] + size[t]) j += 1;     
        next[t][i] = j; 
      }
    }
    
    const int S = std::min(p, n-1);
    std::vector< std::vector<int> > dp(n+1, std::vector<int>(n+1, q+1));
    for (int i = 0;i <= S; ++i) dp[n][i] = 0;
    
    for (int i = n-1;i >= 0; --i) {
      for (int s = S; s >= 0; --s) {
        int& res = dp[i][s];
        res = std::min(res, dp[next[1][i]][s]+1);
        res = std::min(res, dp[next[0][i]][s+1]);
      }
    }

    if (dp[0][0] > q) l = w+1;
    else r = w;
  
  }
    
  std::cout << l;
}

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