Advertisement
mickypinata

USACO-T042: Humble Numbers

Dec 20th, 2021
864
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: humble
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef long long lli;
  11.  
  12. const int N = 1e5 + 5;
  13. const int K = 100 + 5;
  14.  
  15. lli dp[N];
  16. int ptr[K], arr[K];
  17.  
  18. int main(){
  19.     freopen("humble.in", "r", stdin);
  20.     freopen("humble.out", "w", stdout);
  21.  
  22.     int n, tr;
  23.     scanf("%d%d", &n, &tr);
  24.     for(int i = 1; i <= n; ++i){
  25.         scanf("%d", &arr[i]);
  26.     }
  27.     dp[0] = 1;
  28.     for(int x = 1; x <= tr; ++x){
  29.         lli mn = 1e18;
  30.         for(int i = 1; i <= n; ++i){
  31.             while(arr[i] * dp[ptr[i]] <= dp[x - 1]){
  32.                 ++ptr[i];
  33.             }
  34.             mn = min(mn, arr[i] * dp[ptr[i]]);
  35.         }
  36.         dp[x] = mn;
  37.     }
  38.     cout << dp[tr] << '\n';
  39.  
  40.     fclose(stdin);
  41.     fclose(stdout);
  42.     return 0;
  43. }
  44.  
Advertisement
RAW Paste Data Copied
Advertisement