fork download
  1. #include<bits/stdc++.h>
  2. #include <cstdio>
  3. using namespace std;
  4. #define ll long long
  5. #define PB push_back
  6. #define ld long double
  7. #define ff first
  8. #define ss second
  9. # define st(v) (v).begin(),(v).end()
  10. #define pr pair<int,int>
  11. using namespace std::chrono;
  12. const int N = 1e5+4 , M=N,inf=(int)1e9;
  13. const ll mod=998244353;
  14. int fastAbs(int n) { return (n ^ (n >> 31)) - (n >> 31); }
  15. ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
  16. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  17. ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
  18. int ans ;
  19. //map< pair<int,int> , int > mp;
  20. const int dx[4] = {1,0,0,-1};
  21. const int dy[4] = {0,-1,1,0};
  22. bool comp( pair < ll , pair < ll , ll > > x , pair < ll , pair < ll , ll > > y){
  23. return (x.ss.ss * y.ff) >= ( y.ss.ss * x.ff );
  24. }
  25. void solve( int x ){
  26. int n ;
  27. cin >> n ;
  28. vector < pair < ll , pair < ll , ll > > > a(n);
  29. for( int i = 0 ; i < n ; i++){
  30. cin >> a[i].ff >> a[i].ss.ff >> a[i].ss.ss ;
  31. }
  32. sort(st(a),comp);
  33. const int nmax = 10002 ;
  34. vector < vector < ll > > dp( n , vector < ll > (nmax,0));
  35. for( int i = 0 ; i < nmax ; i++){
  36. if(i >= a[0].ff)
  37. dp[0][i] = max( (ll)0 , a[0].ss.ff - a[0].ss.ss * (i-a[0].ff) ) ;
  38. }
  39. for( int i = 1 ; i < n ; i++){
  40. for( int j = 0 ; j < nmax ; j++){
  41. if(j>=a[i].ff){
  42. dp[i][j] = max( dp[i-1][j] , dp[i-1][j-a[i].ff] + max( (ll)0 , a[i].ss.ff - a[i].ss.ss *(j-a[i].ff))) ;
  43. }
  44. else{
  45. dp[i][j] = max((ll)0,dp[i-1][j]);
  46. }
  47. }
  48. }
  49. ll maxm = 0 ;
  50. for( int i = 0 ; i < nmax ; i++){
  51. maxm = max( dp[n-1][i], maxm);
  52. }
  53. cout << "Case #" << x << ": " << maxm << "\n";
  54. }
  55. int main()
  56. {
  57. ios_base::sync_with_stdio(false);
  58. cin.tie(NULL);
  59. cout.tie(NULL);
  60. int q=1;
  61. cin >> q;
  62. for( int i = 0 ; i < q ; i++){
  63. solve(i+1);
  64. }
  65. }
  66. /*
  67.   update - o(1) - log time
  68. */
  69.  
Success #stdin #stdout 0s 15360KB
stdin
3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
stdout
Case #1: 105
Case #2: 8
Case #3: 500