fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "SIRLOCKHOME"
  5. #define all(x) (x).begin(), (x).end()
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> ii;
  9.  
  10. const int MAX_M = 400;
  11. const int MAX_N = 70;
  12. const int MOD = (int)1e9 + 7;
  13.  
  14. template <class X, class Y>
  15. bool maximize(X& x, const Y& y) {
  16.     if (x >= y) return false;
  17.     x = y;
  18.     return true;
  19. };
  20. template <class X, class Y>
  21. bool minimize(X& x, const Y& y) {
  22.     if (x <= y) return false;
  23.     x = y;
  24.     return true;
  25. };
  26.  
  27. int m, n;
  28. string a[MAX_M + 5];
  29.  
  30. bool cmp(const string& a, const string& b) {
  31.     int i = 0, j = 0;
  32.     while (i + 1 < a.size() && a[i] == '0') i++;
  33.     while (j + 1 < b.size() && b[j] == '0') j++;
  34.  
  35.     int szA = (int)a.size() - i;
  36.     int szB = (int)b.size() - j;
  37.     if (szA < szB) return true;
  38.     if (szA > szB) return false;
  39.  
  40.     for (int k = 0; k < szA; k++) {
  41.         if (a[i + k] < b[i + k]) return true;
  42.         if (a[i + k] > b[i + k]) return false;
  43.     };
  44.  
  45.     return false;
  46. };
  47.  
  48. namespace SUBTASK_12 {
  49.     const int M = MAX_M;
  50.     const int V = 1e5;
  51.     const int INF = 1e9;
  52.  
  53.     int dp[M + 5][V + 5];
  54.  
  55.     int cost(string x, string y) {
  56.         string pad = "";
  57.         int diff = abs((int)x.size() - (int)y.size());
  58.  
  59.         for (int i = 0; i < diff; i++) pad += '0';
  60.         if (x.size() < y.size())
  61.             x = pad + x;
  62.         else
  63.             y = pad + y;
  64.  
  65.         int res = 0;
  66.         for (int i = 0; i < x.size(); i++) {
  67.             if (x[i] != y[i]) res++;
  68.         };
  69.  
  70.         return res;
  71.     };
  72.  
  73.     string addPad(int num) {
  74.         string ret = to_string(num);
  75.         int diff = n - (int)ret.size();
  76.         string pad = "";
  77.         for (int i = 0; i < diff; i++) pad += '0';
  78.         return (pad + ret);
  79.     };
  80.  
  81.     void Trace(int idx, int cur) {
  82.         if (idx == 1) {
  83.             cout << addPad(cur) << '\n';
  84.             return;
  85.         };
  86.  
  87.         int c = cost(to_string(cur), a[idx]);
  88.         for (int val = cur - 1; val >= 0; val--) {
  89.             if (dp[idx - 1][val] + c == dp[idx][cur]) {
  90.                 Trace(idx - 1, val);
  91.                 cout << addPad(cur) << '\n';
  92.                 return;
  93.             };
  94.         };
  95.     };
  96.  
  97.     void Solve() {
  98.         int maxVal = 1;
  99.         for (int i = 1; i <= n; i++) maxVal *= 10;
  100.         maxVal--;
  101.  
  102.         for (int i = 0; i <= m; i++) {
  103.             for (int j = 0; j <= maxVal; j++) {
  104.                 dp[i][j] = INF;
  105.             };
  106.         };
  107.  
  108.         for (int cur = 0; cur <= maxVal; cur++) {
  109.             dp[1][cur] = cost(to_string(cur), a[1]);
  110.         };
  111.  
  112.         for (int i = 2; i <= m; i++) {
  113.             int minDp = INF;
  114.             for (int cur = 1; cur <= maxVal; cur++) {
  115.                 minimize(minDp, dp[i - 1][cur - 1]);
  116.                 dp[i][cur] = minDp + cost(to_string(cur), a[i]);
  117.             };
  118.         };
  119.  
  120.         int res = INF;
  121.         int lastVal = maxVal;
  122.         for (int i = 0; i <= maxVal; i++)
  123.             if (minimize(res, dp[m][i])) lastVal = i;
  124.  
  125.         cout << res << '\n';
  126.  
  127.         Trace(m, lastVal);
  128.     };
  129. };  // namespace SUBTASK_12
  130.  
  131. int main() {
  132.     ios_base::sync_with_stdio(0);
  133.     cin.tie(0);
  134.     if (fopen(TASK ".INP", "r")) {
  135.         freopen(TASK ".INP", "r", stdin);
  136.         freopen(TASK ".OUT", "w", stdout);
  137.     };
  138.  
  139.     cin >> m >> n;
  140.     for (int i = 1; i <= m; i++) {
  141.         cin >> a[i];
  142.     };
  143.  
  144.     SUBTASK_12::Solve();
  145. };
  146.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/Evw4aN
language:
C++14 (gcc 8.3)
created:
12 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!