fork download
copy 
  1. //84104971101048411497 - Can you guess what does this mean?
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef complex<double> point;
  8. #define mapii map<int, int>
  9. #define debug(a) cout << #a << ": " << a << endl
  10. #define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
  11. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  12. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  13. #define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
  14. #define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
  15. #define ii pair<int, int>
  16. #define iii pair<int, ii>
  17. #define ff first
  18. #define ss second
  19. #define mp make_pair
  20. #define pb push_back
  21. #define maxN 1005
  22. #define oo 1000000000000000007LL
  23. #define sz(a) (int)a.size()
  24.  
  25. const double PI = acos(-1.0);
  26.  
  27. double fRand(double fMin, double fMax)
  28. {
  29.     double f = (double)rand() / RAND_MAX;
  30.     return fMin + f * (fMax - fMin);
  31. }
  32.  
  33. template <class T>
  34. T min(T a, T b, T c) {
  35.     return min(a, min(b, c));
  36. }
  37.  
  38. template <class T>
  39. T max(T a, T b, T c) {
  40.     return max(a, max(b, c));
  41. }
  42.  
  43. int nTest, R, B, C, M[maxN], S[maxN], P[maxN];
  44.  
  45. bool Check(ll x) {
  46.     vector<int> b;
  47.     fto(i, 1, C)
  48.         if (x >= P[i]) b.pb(min(1LL*M[i], (x-P[i])/S[i]));
  49.  
  50.     sort(b.begin(), b.end());
  51.     reverse(b.begin(), b.end());
  52.  
  53.     ll sum = 0;
  54.     fto(i, 0, min(sz(b), R)-1) sum += b[i];
  55.     return sum >= B;
  56. }
  57.  
  58. int main () {
  59.     scanf("%d", &nTest);
  60.     fto(iTest, 1, nTest) {
  61.         printf("Case #%d: ", iTest);
  62.         scanf("%d%d%d", &R, &B, &C);
  63.         fto(i, 1, C) scanf("%d%d%d", &M[i], &S[i], &P[i]);
  64.  
  65.         ll lo = 1, hi = oo, res = 0;
  66.         while (lo <= hi) {
  67.             ll mid = (lo+hi)/2;
  68.             if (Check(mid)) {
  69.                 res = mid;
  70.                 hi = mid-1;
  71.             } else lo = mid+1;
  72.         }
  73.  
  74.         printf("%lld\n", res);
  75.     }
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1
stdout
copy 
Case #1: 5
Case #2: 4
Case #3: 7
https://ideone.com/WLHBJ0
language:
C++14 (clang 8.0)
created:
6 years 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!