fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. #define pb push_back
  4. #define mpp make_pair
  5. #define F first
  6. #define S second
  7. using namespace std;
  8.  
  9. const int N=5e2+5;
  10. const ll infi=1e18+5;
  11. const ll mod=1e9+7;
  12.  
  13. pair<ll,pair<ll,ll> >x[505];
  14. ll s[N],e[N],l[N];
  15. ll dp[10005][105];
  16. ll n;
  17.  
  18. ll fun(ll t,ll idx)
  19. {
  20.     if(idx==0)
  21.     return 0;
  22.     ll &var=dp[t][idx];
  23.     if(var!=-1)
  24.         return var;
  25.     ll et=x[idx].S.F;
  26.     ll energy=x[idx].S.S;
  27.     ll cost=x[idx].F;
  28.     var=max((ll)0,energy-cost*t) + fun(t+et,idx-1);
  29.     var=max(var,fun(t,idx-1));
  30.  
  31.     return var;
  32. }
  33. int main()
  34. {
  35.     ll tt;
  36.     cin>>tt;
  37.  
  38.     for(ll ii=1;ii<=tt;ii++)
  39.     {
  40.     	cout<<"Case #"<<ii<<": ";
  41.         cin>>n;
  42.         ll i;
  43.         for(i=1;i<=n;i++)
  44.         {
  45.             cin>>s[i]>>e[i]>>l[i];
  46.             x[i]=mpp(l[i],mpp(s[i],e[i]));
  47.         }
  48.         sort(x+1,x+n+1);
  49.         memset(dp,-1,sizeof(dp));
  50.         ll ans=fun(0,n);
  51.  
  52.         cout<<ans<<"\n";
  53.     }
  54. }
Success #stdin #stdout 0s 11644KB
comments (?)
stdin
copy 
2
3
10 4 1000
10 3 1000
10 8 1000
2
5 300 50
5 200 0
stdout
copy 
Case #1: 8
Case #2: 500
https://ideone.com/C3Z9HZ
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!