oj.uz

Submission #652140

# Submission time Handle Problem Language Result Execution time Memory
652140 2022-10-21T12:43:55 Z pauloamed Watching (JOI13_watching) C++14
100 / 100
 422 ms 16088 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2010;


int dp[MAXN][MAXN];
int v[MAXN];
int N, P, Q;

int go[MAXN][2];

bool can(int w){
  int last_0 = 0;
  int last_1 = 0;
  for(int i = 0; i < N; ++i){
    while(last_0 < N && v[last_0] - v[i] <= w - 1)
      last_0++;

    while(last_1 < N && v[last_1] - v[i] <= 2LL*w - 1)
      last_1++;

    go[i][0] = last_0;
    go[i][1] = last_1;

    // cout << i << " " << last_0 << " " << last_1 << "\n";
  }

  int maxp = min(N, P);
  for(int i = 0; i <= N; ++i){
    for(int j = 0; j <= maxp; ++j){
      dp[i][j] = INT_MAX;
    }
  }

  // P: w 0
  // Q: 2w 1
  dp[0][0] = 0;
  for(int i = 0; i < N; ++i){
    for(int j = 0; j <= maxp; ++j){
      if(dp[i][j] == INT_MAX) continue;
      dp[go[i][0]][j + 1] = min(dp[go[i][0]][j + 1], dp[i][j]);
      dp[go[i][1]][j] = min(dp[go[i][1]][j], dp[i][j] + 1);
    }
  }

  // cout << w << ":\n";
  int mini = INT_MAX;
  for(int j = 0; j <= maxp; ++j){
    // cout << j << " : " << dp[N][j] << "\n";
    mini = min(mini, dp[N][j]);
  }
  return mini <= Q;
}

int main(){
  cin.tie(NULL)->sync_with_stdio(false);
  cin >> N >> P >> Q;
  for(int i = 0; i < N; ++i) cin >> v[i];
  sort(v, v + N);

  // can(3);
  // return 0;

  int pot = (1 << 30);
  int ans = 0;
  while(pot){
    int mans = ans + pot;
    if(!can(mans)) ans = mans;
    pot /= 2;
  }
  cout << ans + 1 << "\n";
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8404 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 369 ms 16088 KB Output is correct
4 Correct 402 ms 16088 KB Output is correct
5 Correct 36 ms 8996 KB Output is correct
6 Correct 422 ms 16088 KB Output is correct
7 Correct 8 ms 8404 KB Output is correct
8 Correct 39 ms 9300 KB Output is correct
9 Correct 169 ms 14244 KB Output is correct
10 Correct 406 ms 16088 KB Output is correct
11 Correct 40 ms 9044 KB Output is correct
12 Correct 284 ms 16048 KB Output is correct
13 Correct 10 ms 8404 KB Output is correct
14 Correct 9 ms 8424 KB Output is correct
15 Correct 8 ms 8404 KB Output is correct