YEZAELP

PROG-1080: สามเหลี่ยมอีกครั้ง (triagain)

Jan 3rd, 2021 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 2e9;
  5. int ar[30010];
  6. int n;
  7.  
  8. int BS(int ab, int l){
  9.     int r = n, idx = -INF;
  10.     while(l <= r){
  11.         int mid = (l + r) / 2;
  12.         if(ar[mid]< ab){
  13.             idx = max(idx, mid);
  14.             l = mid + 1;
  15.         }
  16.         else r = mid - 1;
  17.     }
  18.     return idx;
  19. }
  20.  
  21. int main(){
  22.  
  23.     scanf("%d",&n);
  24.  
  25.     int prev = 0;
  26.     for(int i = 1; i <= n; i++){
  27.         scanf("%d", &ar[i]);
  28.     }
  29.  
  30.     sort(ar + 1, ar + n + 1);
  31.  
  32.     int mx = 0;
  33.     for(int i = 1; i <= n-2; i++){
  34.         mx = max(mx, BS(ar[i] + ar[i+1], i+2) - i + 1);
  35.     }
  36.  
  37.     if(mx == 0) printf("%d", n);
  38.     else printf("%d", mx);
  39.  
  40.     return 0;
  41. }
  42.  
RAW Paste Data Copied