oj.uz

Submission #444938

# Submission time Handle Problem Language Result Execution time Memory
444938 2021-07-15T22:23:39 Z ivan_tudor Watching (JOI13_watching) C++14
100 / 100
 258 ms 16068 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int v[N];
int dp[N][N];
int n, p, q;
bool check(int w){
  int lst, lst2;
  for(int i =0 ; i<N; i++){
    for(int j = 0; j < N; j++){
      dp[i][j] = INT_MAX;
      dp[0][j] = 0;
    }
  }
  lst = lst2 = 0;
  for(int i =1 ; i<=n; i++){
    while(lst < i && v[i] - v[lst + 1] + 1 > w)
      lst++;
    while(lst2 < i && v[i] - v[lst2 + 1] + 1 > 2*w)
      lst2++;
    for(int j = 0; j <= i; j++ ){
      if(dp[lst][j] != INT_MAX)
        dp[i][j] = min(dp[i][j], dp[lst][j] + 1);
      if(j)
        dp[i][j] = min(dp[i][j], dp[lst2][j-1]);
    }
  }
  for(int i = 0; i <=q; i++){
    if(dp[n][i] <=p)
      return true;
  }
  return false;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>n>>p>>q;
  for(int i =1 ; i<=n; i++){
    cin>>v[i];
  }
  sort(v+1, v+n+1);
  if(p + q >= n){
    cout<<"1";
    return 0;
  }
  int pas = 0;
  for(int p2 = 1<<29; p2>0; p2>>=1){
    if(check(pas + p2) == false)
      pas+=p2;
  }
  cout<<pas + 1;
  return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16028 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 122 ms 15948 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 123 ms 16068 KB Output is correct
8 Correct 122 ms 16032 KB Output is correct
9 Correct 124 ms 15940 KB Output is correct
10 Correct 122 ms 15980 KB Output is correct
11 Correct 121 ms 16028 KB Output is correct
12 Correct 122 ms 16068 KB Output is correct
13 Correct 121 ms 15940 KB Output is correct
14 Correct 124 ms 15928 KB Output is correct
15 Correct 121 ms 16032 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 16052 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 230 ms 16064 KB Output is correct
8 Correct 239 ms 16056 KB Output is correct
9 Correct 242 ms 16016 KB Output is correct
10 Correct 258 ms 16052 KB Output is correct
11 Correct 253 ms 16004 KB Output is correct
12 Correct 249 ms 16052 KB Output is correct
13 Correct 244 ms 16060 KB Output is correct
14 Correct 233 ms 15948 KB Output is correct
15 Correct 231 ms 15980 KB Output is correct