fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. const int LINF = (int)2e18;
  6. const int mxN = (int)1e2+10;
  7. int n, A, B, a[mxN], x[mxN], y[mxN], c[mxN];
  8.  
  9. bool works(int remA, int remB){
  10.     for(int i = 0; i < n; i++)
  11.         if((A-remA)*x[i] + (B-remB)*y[i] > c[i])
  12.             return false;
  13.     return true;
  14. }
  15.  
  16. int bin(int remA){
  17.     int l = 0, r = B-1;
  18.     if(!works(remA,r) or remA<0 or remA>=A) return LINF;
  19.     while(l<r){
  20.         int mid = (l+r)/2;
  21.         if(works(remA, mid)) r=mid;
  22.         else l=mid+1;
  23.     }
  24.     return remA+l;
  25. }
  26.  
  27. void solve(){
  28.     cin >> n >> A >> B; int ans = A+B-2;
  29.     for(int i = 0; i < n; i++) cin >> x[i] >> y[i] >> c[i];
  30.     for(int _ = 0; _ < 2; _++){
  31.         int l = 0, r = A-1;
  32.         while(r-l>3){
  33.             int m = (r-l)/3;
  34.             int X = bin(l+m), Y = bin(r-m);
  35.             if(X==LINF or X>Y) l+=m;
  36.             else r-=m;
  37.         }
  38.         for(int i = l; i <= r; i++)
  39.             ans = min(ans, bin(i));
  40.         swap(A,B);
  41.         for(int i = 0; i < n; i++) swap(x[i],y[i]);
  42.     }
  43.     cout << ans << "\n";
  44. }
  45.  
  46. int32_t main() {
  47.     ios_base::sync_with_stdio(false); cin.tie(0);
  48. 	int t = 1; cin >> t;
  49.     while(t--) solve();
  50. }
  51.  
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-2
https://ideone.com/fC0YgD
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!