fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Case #1: 105
Case #2: 8
Case #3: 500
https://ideone.com/PyUzLp
language:
C++14 (gcc 8.3)
created:
4 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!