#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define int unsigned long long int
using namespace std;
typedef unsigned long long ll;
const int T = 350;
const int MOD = 1e9 + 7;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n , t , k;
cin >> n >> t >> k;
vector<int> ds(k + 1);
for(int i = 1 ; i <= k ; i++)cin >> ds[i];
vector<int> rng(1e6);
vector<int> fstrng(1e6);
fstrng[0] = 1;
int ans = 0;
while(true){
int bestdeal = 0 , best_valu = 1e18;
for(int i = 0 ;i < k ; i++){
if(fstrng[i] == 0)continue;
if(ds[i + 1] + (fstrng[i] - 1) * t <= best_valu){
best_valu = ds[i + 1] + (fstrng[i] - 1) * t;
bestdeal = i;
}
}
int cmt = (1ll << (1 + fstrng[bestdeal]));
if(n <= cmt){
ans += n * best_valu;
break;
}else{
ans += cmt * best_valu;
n -= cmt;
}
if(fstrng[bestdeal + 1] == 0)fstrng[bestdeal + 1] = fstrng[bestdeal];
if(rng[fstrng[bestdeal] + 1] == bestdeal)fstrng[bestdeal]++;
else fstrng[bestdeal] = 0;
rng[fstrng[bestdeal]]++;
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |