oj.uz

Submission #564895

# Submission time Handle Problem Language Result Execution time Memory
564895 2022-05-19T23:12:19 Z SSRS Watching (JOI13_watching) C++14
50 / 100
 1000 ms 12128 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 + 1), R2(N + 1);
    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();
    }
    R1[N] = N;
    R2[N] = N;
    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 <= P; 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);
      }
    }
    if (dp[N][P] <= Q){
      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 5 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 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 3 ms 212 KB Output is correct
12 Correct 3 ms 212 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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1050 ms 12128 KB Time limit exceeded
4 Halted 0 ms 0 KB -