Advertisement
mickypinata

USACO-T041: Score Inflation

Dec 19th, 2021
765
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: inflate
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 1e4 + 5;
  11.  
  12. int score[N], tme[N], dp[2][N];
  13.  
  14. int main(){
  15.     freopen("inflate.in", "r", stdin);
  16.     freopen("inflate.out", "w", stdout);
  17.  
  18.     int limTime, n;
  19.     scanf("%d%d", &limTime, &n);
  20.     for(int i = 1; i <= n; ++i){
  21.         scanf("%d%d", &score[i], &tme[i]);
  22.     }
  23.     for(int i = n; i >= 1; --i){
  24.         int cur = i % 2;
  25.         int nxt = cur ^ 1;
  26.         for(int t = 1; t <= limTime; ++t){
  27.             int mx = dp[nxt][t];
  28.             if(t >= tme[i]){
  29.                 mx = max(mx, score[i] + dp[cur][t - tme[i]]);
  30.             }
  31.             dp[cur][t] = mx;
  32.         }
  33.     }
  34.     cout << dp[1][limTime] << '\n';
  35.  
  36.     fclose(stdin);
  37.     fclose(stdout);
  38.     return 0;
  39. }
  40.  
Advertisement
RAW Paste Data Copied
Advertisement