oj.uz

Submission #564900

# Submission time Handle Problem Language Result Execution time Memory
564900 2022-05-19T23:20:24 Z SSRS Watching (JOI13_watching) C++14
100 / 100
 748 ms 16068 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
int main(){
  int N, P, Q;
  cin >> N >> P >> Q;
  P = min(P, N);
  Q = min(Q, N);
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  int tv = 500000000, fv = 0;
  vector<vector<int>> dp(N + 1, vector<int>(P + 1, INF));
  while (tv - fv > 1){
    int mid = (tv + fv) / 2;
    vector<int> R1(N), R2(N);
    for (int i = 0; i < N; i++){
      R1[i] = lower_bound(A.begin(), A.end(), A[i] + mid) - A.begin();
      R2[i] = lower_bound(A.begin(), A.end(), A[i] + mid * 2) - A.begin();
    }
    for (int i = 0; i <= N; i++){
      for (int j = 0; j <= P; j++){
        dp[i][j] = INF;
      }
    }
    dp[0][0] = 0;
    for (int i = 0; i < N; i++){
      for (int j = 0; j <= min(P, i); j++){
        if (j < P){
          dp[R1[i]][j + 1] = min(dp[R1[i]][j + 1], dp[i][j]);
        }
        dp[R2[i]][j] = min(dp[R2[i]][j], dp[i][j] + 1);
      }
    }
    bool ok = false;
    for (int i = 0; i <= P; i++){
      if (dp[N][i] <= Q){
        ok = true;
      }
    }
    if (ok){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  cout << tv << endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 224 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 424 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 676 ms 12132 KB Output is correct
4 Correct 700 ms 16044 KB Output is correct
5 Correct 57 ms 996 KB Output is correct
6 Correct 724 ms 16068 KB Output is correct
7 Correct 13 ms 468 KB Output is correct
8 Correct 88 ms 1376 KB Output is correct
9 Correct 447 ms 6296 KB Output is correct
10 Correct 748 ms 15280 KB Output is correct
11 Correct 66 ms 1080 KB Output is correct
12 Correct 559 ms 8088 KB Output is correct
13 Correct 15 ms 448 KB Output is correct
14 Correct 17 ms 468 KB Output is correct
15 Correct 19 ms 468 KB Output is correct