ulvis.paste.net

Paste Search Dynamic
Recent pastes
Case
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MAXN = 110;
  7. const int MAXS = 110;
  8.  
  9. int N;
  10. ll S[MAXN];
  11. ll E[MAXN];
  12. ll L[MAXN];
  13. int inds[MAXN];
  14.  
  15. const int MAXT = MAXN * MAXS;
  16. int T;
  17. ll dp[MAXT];
  18.  
  19. int main() {
  20.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  21.     int N_CASES; cin >> N_CASES;
  22.     for (int case_ = 1; case_ <= N_CASES; case_ ++) {
  23.         cin >> N;
  24.         for (int i = 0; i < N; i++) {
  25.             cin >> S[i] >> E[i] >> L[i];
  26.         }
  27.         for (int i = 0; i < N; i++) {
  28.             inds[i] = i;
  29.         }
  30.         sort(inds, inds + N, [&](int a, int b) {
  31.            return S[a] * L[b] < S[b] * L[a];
  32.         });
  33.         memset(dp, 0, sizeof(dp));
  34.         T = 0;
  35.         for (int z = 0; z < N; z++) {
  36.             int i = inds[z];
  37.             for (int t = T; t >= 0; t--) {
  38.                 dp[t + S[i]] = max(dp[t + S[i]], dp[t] + max(0ll, E[i] - L[i] * t));
  39.             }
  40.             T += S[i];
  41.         }
  42.        
  43.         ll ans = 0;
  44.         for (int t = 0; t <= T; t++) ans = max(ans, dp[t]);
  45.        
  46.         cout << "Case #" << case_ << ": " << ans << '\n';
  47.     }
  48. }
Parsed in 0.009 seconds