USACO-T042: Humble Numbers

/*
ID: mickyta1
TASK: humble
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e5 + 5;
const int K = 100 + 5;

lli dp[N];
int ptr[K], arr[K];

int main(){
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);

    int n, tr;
    scanf("%d%d", &n, &tr);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    dp[0] = 1;
    for(int x = 1; x <= tr; ++x){
        lli mn = 1e18;
        for(int i = 1; i <= n; ++i){
            while(arr[i] * dp[ptr[i]] <= dp[x - 1]){
                ++ptr[i];
            }
            mn = min(mn, arr[i] * dp[ptr[i]]);
        }
        dp[x] = mn;
    }
    cout << dp[tr] << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}