fork download
copy 
  1. // Đạt đz s1 tg
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define f first
  6. #define s second
  7. #define mod 1000000007
  8. #define PB push_back
  9. #define PF push_front
  10. #define inf 10000007
  11. #define round(m,n) setprecision((int)m) << fixed << double(n)
  12. #define ll long long
  13. #define int long long
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define pii pair<int, int>
  16. #define TASK "bus"
  17.  
  18. using namespace std;
  19.  
  20. void ADD(int &x, int y){
  21.     x += y;
  22.     if (x >= mod) x -= mod;
  23.     if (x < 0) x += mod;
  24. }
  25.  
  26. int n, m, maxcustomer = 0;
  27. int a[200005];
  28. vector<int> p[200005];
  29.  
  30. int check(int mid){
  31.     int S = 0;
  32.     int cnt = 0;
  33.     for(int i = 1; i <= n; i++){
  34.         for(auto x : p[i])
  35.         if(S + mid >= x) cnt++;
  36.         S += a[i];
  37.     }
  38.     return (cnt >= maxcustomer);
  39. }
  40.  
  41. int Binary(int l, int r){
  42.     while(r - l > 1){
  43.         int mid = (r + l) / 2;
  44.         if(check(mid)) r = mid;
  45.         else l = mid;
  46.     }
  47.     return r;
  48. }
  49.  
  50. signed main(){
  51.     ios_base::sync_with_stdio(0);
  52.     cin.tie(0); cout.tie(0);
  53.  
  54.     if(fopen(TASK".INP", "r")){
  55.         freopen(TASK".INP", "r", stdin);
  56.         freopen(TASK".OUT", "w", stdout);
  57.     }
  58.  
  59.     cin >> n >> m;
  60.     int S = 0;
  61.     for(int i = 1; i <= n; i++){
  62.         cin >> a[i];
  63.         int sz;
  64.         cin >> sz;
  65.         for(int j = 1; j <= sz; j++){
  66.             int x;
  67.             cin >> x;
  68.             p[i].PB(x);
  69.         }
  70.         S += a[i];
  71.     }
  72.  
  73.     int SS = 0;
  74.     for(int i = 1; i <= n; i++){
  75.         for(auto x : p[i])
  76.         if(SS + 2e18 >= x && x >= SS) maxcustomer++;
  77.         SS += a[i];
  78.     }
  79.     maxcustomer = min(maxcustomer, m);
  80.  
  81.     cout << Binary(-1, (1 << 31) - 1) + S;
  82. }
Success #stdin #stdout 0.01s 9164KB
comments (?)
stdin
copy 
3 2
3 2 4 3
1 3 6 3 7
5 1 5
stdout
copy 
10
https://ideone.com/XAad8b
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!