YEZAELP

TOI17: Noodle

Jan 4th, 2022 (edited)
280
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const int inf = 2e9;
  6. const int N = 1e5 + 10;
  7. const int M = 1e2 + 10;
  8. const int K = 4e3 + 10;
  9. int n, m, k;
  10. int ar[N];
  11.  
  12. bool Check(lli check){
  13.     priority_queue <int, vector <int>, greater <int>> pq;
  14.     int cnt = 0, sum = 0, sz = 0;
  15.     for(int i=1;i<=n;i++){
  16.         sum += ar[i];
  17.         pq.push(ar[i]);
  18.  
  19.         if(pq.size() > k){
  20.             sum -= pq.top();
  21.             pq.pop();
  22.         }
  23.  
  24.         if((lli) sum >= check and pq.size() == k){
  25.             cnt ++;
  26.             sum = 0;
  27.             while(!pq.empty()) pq.pop();
  28.         }
  29.     }
  30.     return cnt >= m;
  31. }
  32.  
  33. int main(){
  34.  
  35.     scanf("%d %d %d", &n, &m, &k);
  36.  
  37.     for(int i=1;i<=n;i++){
  38.         scanf("%d", &ar[i]);
  39.     }
  40.  
  41.     lli l = 0, r = inf, mx = -inf;
  42.     while(l <= r){
  43.         lli mid = (l + r) / 2;
  44.         bool Ch = Check(mid);
  45.         if(Ch) l = mid + 1, mx = max(mx, mid);
  46.         else r = mid - 1;
  47.     }
  48.  
  49.     printf("%lld", mx);
  50.  
  51.     return 0;
  52. }
  53.  
  54. /*
  55.  
  56. Binary Search หา a ที่มากที่สุด
  57. โดย a คือผลรวมขั้นต่ำที่ทำให้สามารถเลือกได้ k ตัว เป็นจำนวน m ช่วง
  58.  
  59. ในการเลือก k ตัวให้ได้ m ช่วงจะนำ priority queue มาใช้โดยให้เรียงจากน้อยไปมาก (เพื่อให้ดึงตัวที่น้อยที่สุดออกมา เพราะ หากครบ k ตัวแล้ว sum ไม่สามารถทำให้ >= check ได้แปลว่า หากมีตัวที่มากกว่าตัวที่น้อยที่สุดแล้ว ควรเอาตัวที่น้อยที่สุดนั้นออกไป)
  60.  
  61. เช่น A > B > C > D, sum = A + B + C + D
  62. ใน  pq : D C B A มีตัวใหม่เข้ามาที่มากกว่า D ให้ดึง D (ลบ D ออกจาก sum ด้วย, sum -= D)
  63.  
  64. */
RAW Paste Data Copied