Submission #373455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373455	2021-03-04T17:00:35 Z	Halit	Watching (JOI13_watching)	C++17	100 / 100	669 ms	16544 KB

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.0 / 50.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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