fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 100010;
  5. const ll INF = 1000000000000000LL;
  6.  
  7. int n;
  8. ll p;
  9. int a[N];
  10. ll v[12];
  11. ll fac[12];
  12. // d(i, j, k) : smallest cost of the ith digit, number j, compress k times
  13. ll d[12][12][12];
  14.  
  15. void init() {
  16.   for (int i = 0; i <= 9; i++)
  17.     for (int j = 0; j <= 9; j++)
  18.       for (int k = 0; k <= 9; k++)
  19.         d[i][j][k] = INF;
  20.  
  21.   for (int i = 0; i <= 9; i++) {
  22.     for (int k = 0; k <= 9; k++)
  23.       d[i][0][k] = 0;
  24.     for (int j = 1; j <= 9; j++) {
  25.       d[i][j][0] = fac[i] * j * p;
  26.       for (int k = 1; k <= 9; k++) {
  27.         d[i][j][k] = d[i][j][k - 1];
  28.         for (int t = 0; t < j; t++) {
  29.           d[i][j][k] = min(d[i][j][k], d[i][t][k - 1] + v[j - t]);
  30.           d[i][j][k] = min(d[i][j][k], d[i][t][k] + fac[i] * (j - t) * p);
  31.         }
  32.       }
  33.     }
  34.   }
  35.   // cout << d[1][1][1] << endl;
  36.   // cout << d[0][3][0] << endl;
  37.   // cout << d[1][1][0] << endl;
  38.   // cout << d[0][3][1] << endl;
  39. }
  40.  
  41. ll calc(int x) {
  42.   if (x == 1) {
  43.     return p;
  44.   }
  45.  
  46.   int b[12];
  47.   int cnt = 0;
  48.   int t = x;
  49.   while (t) {
  50.     b[cnt++] = t % 10;
  51.     t /= 10;
  52.   }
  53.   ll o = p;
  54.   int mx = 0;
  55.   for (int i = 0; i < cnt; i++) {
  56.     o += v[b[i]];
  57.     mx = max(mx, b[i]);
  58.   }
  59.  
  60.   ll ret = o;
  61.   // compress times
  62.   for (int i = 0; i <= 9; i++) {
  63.     ll now = p * i;
  64.     // for each digit
  65.     for (int j = 0; j < cnt; j++) {
  66.       now += d[j][b[j]][i];
  67.     }
  68.     if (now < ret)
  69.       ret = now;
  70.   }
  71.   return ret;
  72. }
  73.  
  74. int main() {
  75.   ios_base::sync_with_stdio(false);
  76.   cin.tie(NULL);
  77.  
  78.   fac[0] = 1;
  79.   for (int i = 1; i <= 9; i++)
  80.     fac[i] = fac[i - 1] * 10;
  81.  
  82.   cin >> n >> p;
  83.   for (int i = 0; i < n; i++) {
  84.     string s;
  85.     cin >> s >> a[i];
  86.   }
  87.   for (int i = 0; i <= 9; i++) {
  88.     cin >> v[i];
  89.   }
  90.   init();
  91.   ll ans = 0;
  92.   for (int t = 0; t < n; t++) {
  93.     ans += calc(a[t]);
  94.   }
  95.   cout << ans << endl;
  96.  
  97.   return 0;
  98. }
Success #stdin #stdout 0.01s 5332KB
comments (?)
stdin
copy 
8 5
I 1
L 1
O 9
V 1
E 1
Y 1
O 1
U 1
0 1 2 3 4 5 6 7 8 999
stdout
copy 
53
https://ideone.com/IAD0Vu
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!