oj.uz

Submission #917651

# Submission time Handle Problem Language Result Execution time Memory
917651 2024-01-28T14:03:45 Z Aiperiii Watching (JOI13_watching) C++14
100 / 100
 670 ms 32508 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,p,q;
   cin>>n>>p>>q;
   p=min(n,p);
   q=min(n,q);
   vector <int> a(n);
   for(int i=0;i<n;i++)cin>>a[i];
   sort(all(a));
   int l=0,r=1e10;
   
  while(l+1<r){
      int md=(l+r)/2;
      bool ok=0;
      vector <vector <int> > dp(n+1,vector <int> (p+1,1e9));
      for(int i=0;i<=p;i++)dp[0][i]=0;
      for(int i=1;i<=n;i++){
         auto pos1=lower_bound(all(a),a[i-1]-md*2+1)-a.begin();
         auto pos2=lower_bound(all(a),a[i-1]-md+1)-a.begin();
         for(int j=0;j<=p;j++){
            dp[i][j]=min(dp[i][j],dp[pos1][j]+1);
            if(j>0)dp[i][j]=min(dp[i][j],dp[pos2][j-1]);
         }
      }
      if(dp[n][p]<=q)ok=1;
      if(ok)r=md;
      else l=md;
   }
   cout<<r<<"\n";
}
/*
 13 3 2 33
 66
 99
 10
 83
 68
 19
 83
 93
 53
 15
 66
 75
 */

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 541 ms 24496 KB Output is correct
4 Correct 653 ms 32184 KB Output is correct
5 Correct 25 ms 1800 KB Output is correct
6 Correct 670 ms 32508 KB Output is correct
7 Correct 6 ms 600 KB Output is correct
8 Correct 35 ms 2576 KB Output is correct
9 Correct 227 ms 12456 KB Output is correct
10 Correct 657 ms 30376 KB Output is correct
11 Correct 25 ms 2004 KB Output is correct
12 Correct 320 ms 16040 KB Output is correct
13 Correct 8 ms 600 KB Output is correct
14 Correct 11 ms 820 KB Output is correct
15 Correct 11 ms 788 KB Output is correct