Advertisement
kdzhr

Untitled

Jan 5th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. // D school 19-20 100(Accepted) http://contest.uni-smr.ac.ru/pix/190921/contest-13210-ru.pdf
  2.  
  3. # include <iostream>
  4. # include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     long long n;
  10.     long long k;
  11.     cin >> n >> k;
  12.     long long left = 0;
  13.     long long right = 1000000000;
  14.     vector <long long> m;
  15.     m.resize(n);
  16.     for(long long i = 0; i < n; i++){
  17.         cin >> m[i];
  18.     }
  19.     long long b_cur = 0;
  20.     bool is_good = true;
  21.     for (long long i = 0; i <= n; i++){
  22.         if (i != n){
  23.             if (m[i] > left){
  24.                 b_cur++;
  25.             }
  26.             else{
  27.                 b_cur = 0;
  28.             }
  29.         }
  30.         if (b_cur >= k){
  31.             is_good = false;
  32.             break;
  33.         }
  34.     }
  35.     if (is_good){
  36.         cout << 0;
  37.     }
  38.     else {
  39.         while ((right - left) > 1){
  40.             long long middle = (right + left) / 2;
  41.             b_cur = 0;
  42.             is_good = true;
  43.             for(long long i = 0; i <= n; i++){
  44.                 if (i != n){
  45.                     if (m[i] > middle){
  46.                         b_cur++;
  47.                     }
  48.                     else {
  49.                         b_cur = 0;
  50.                     }
  51.                 }
  52.                 if (b_cur >= k){
  53.                     is_good = false;
  54.                     break;
  55.                 }
  56.             }
  57.             if (!is_good){
  58.                 left = middle;
  59.             }
  60.             else {
  61.                 right = middle;
  62.             }
  63.         }
  64.         cout << right;
  65.     }
  66.     return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement