oj.uz

답안 #373455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373455 2021-03-04T17:00:35 Z Halit 구경하기 (JOI13_watching) C++17
100 / 100
 669 ms 16544 KB 
//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.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 364 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 16352 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 548 ms 16340 KB Output is correct
4 Correct 669 ms 16268 KB Output is correct
5 Correct 315 ms 16540 KB Output is correct
6 Correct 660 ms 16220 KB Output is correct
7 Correct 287 ms 16416 KB Output is correct
8 Correct 312 ms 16544 KB Output is correct
9 Correct 438 ms 16448 KB Output is correct
10 Correct 642 ms 16308 KB Output is correct
11 Correct 301 ms 16308 KB Output is correct
12 Correct 471 ms 16380 KB Output is correct
13 Correct 294 ms 16244 KB Output is correct
14 Correct 290 ms 16272 KB Output is correct
15 Correct 281 ms 16376 KB Output is correct