sadov_a

Ням-ням

Apr 1st, 2020
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #ifdef ONLINE_JUDGE
  4. #pragma GCC optimize("Ofast")
  5. #pragma GCC optimize("no-stack-protector")
  6. #pragma GCC optimize("unroll-loops")
  7. #pragma GCC optimize("fast-math")
  8. #pragma GCC optimize("vpt")
  9. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
  10. #endif
  11.  
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. const char el = '\n';
  18. const int inf = 1000'000'100;
  19. const ll llinf = 1e18, mod = 1000'000'007;
  20. const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
  21.  
  22. #define forn(i, n) for (int i = 0; i < (int)n; ++i)
  23. #define firn(i, n) for (int i = 1; i < (int)n; ++i)
  24. #define all(v) v.begin(), v.end()
  25. #define rall(v) v.rbegin(), v.rend()
  26. #define x first
  27. #define y second
  28. #define debug(x) cout << #x << ": " << x << el
  29.  
  30. template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
  31. template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
  32. template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << el; }
  33. template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }
  34.  
  35. mt19937 rnd(time(nullptr));
  36.  
  37. #define int ll
  38. const int N = 301;
  39. int d[N][N], ans[N][N], d1[N][N][N];
  40. ll st[10] = {1ll, 10ll, 100ll, 1000ll, 10'000ll, 100'000ll, 1000'000ll, 10'000'000ll, 100'000'000ll, 1000'000'00'0ll};
  41. string s;
  42. int n, m, k, mid;
  43. void solve() {
  44.     if ((int)s.size() == 1) {
  45.         firn(j, k + 1) d[0][j] = 0;
  46.         if (s[0] - '0' <= mid) d[0][0] = s[0] - '0';
  47.         else d[0][0] = inf;
  48.     }
  49.     firn(j, k + 1) d[m - 1][j] = 0;
  50.     assert(s.back() != '+');
  51.     if (s.back() - '0' <= mid) d[m - 1][0] = s.back() - '0';
  52.     else d[m - 1][0] = inf;
  53.     for (int j = m - 2; j >= 0; j--) {
  54.         forn(q, k + 1) {
  55.             d[j][q] = inf;
  56.             if (j < m - 2) {
  57.                 int tmp = (s[j] == '0' ? 0 : 1) + (s[j + 1] == '+' ? 0 : 1);
  58.                 if (q >= tmp) uin(d[j][q], d[j + 2][q - tmp]);
  59.             }
  60.             int cc = 0;
  61.             ll tmp = 0;
  62.             for (int c = j; c < m && c < j + 10; c++) {
  63.                 int bb = (s[c + 1] == '+' ? 0 : 1);
  64.                 tmp *= 10ll;
  65.                 if (s[c] != '+' && (s[c] != '0' || c > j)) {
  66.                     tmp += s[c] - '0';
  67.                 }
  68.                 else {
  69.                     tmp += (c > j ? 0 : 1);
  70.                     cc++;
  71.                 }
  72.                 if (cc > q) break;
  73.                 if (c == m - 2) continue;
  74.                 if (c == m - 1) {
  75.                     if (tmp <= mid && q >= cc)
  76.                         uin(d[j][q], (int)tmp);
  77.                     int cnt = 0;
  78.                     if (s[j] >= '2' && s[j] <= '9') {
  79.                         cnt = 1;
  80.                         tmp -= (s[j] - '1') * st[c - j];
  81.                         if (cnt + cc <= q && tmp <= mid) uin(d[j][q], (int)tmp);
  82.                     }
  83.                     for (int e = j + 1; e <= c; e++) {
  84.                         if (s[e] == '0' || s[e] == '+') continue;
  85.                         cnt++;
  86.                         if (cnt + cc > q) break;
  87.                         tmp -= (s[e] - '0') * st[c - e];
  88.                         if (tmp <= mid)
  89.                             uin(d[j][q], (int)tmp);
  90.                     }
  91.                     break;
  92.                 }
  93.                 if (cc + bb > q) continue;
  94.                 if (tmp <= mid)
  95.                     uin(d[j][q], (int)tmp + d[c + 2][q - cc - bb]);
  96.                 int cnt = 0;
  97.                 auto tmp1 = tmp;
  98.                 if (s[j] >= '2' && s[j] <= '9') {
  99.                     cnt = 1;
  100.                     tmp1 -= (s[j] - '1') * st[c - j];
  101.                     if (tmp1 <= mid && cnt + cc + bb <= q) uin(d[j][q], (int)tmp1 + d[c + 2][q - bb - cnt - cc]);
  102.                 }
  103.                 for (int e = j + 1; e <= c; e++) {
  104.                     if (s[e] == '0' || s[e] == '+') continue;
  105.                     cnt++;
  106.                     if (cnt + cc + bb > q) break;
  107.                     tmp1 -= (s[e] - '0') * st[c - e];
  108.                     if (tmp1 <= mid)
  109.                         uin(d[j][q], (int)tmp1 + d[c + 2][q - bb - cnt - cc]);
  110.                 }
  111.             }
  112.         }
  113.     }
  114. }
  115. void vost(int j, int q) {
  116.     if (j == m - 1) {
  117.         if (q > 0) s[j] = '0';
  118.         return;
  119.     }
  120.     if (j < m - 2) {
  121.         int tmp = (s[j] == '0' ? 0 : 1) + (s[j + 1] == '+' ? 0 : 1);
  122.         if (q >= tmp && d[j][q] == d[j + 2][q - tmp]) {
  123.             s[j] = '0';
  124.             s[j + 1] = '+';
  125.             return void(vost(j + 2, q - tmp));
  126.         }
  127.     }
  128.     int cc = 0;
  129.     ll tmp = 0;
  130.     for (int c = j; c < m; c++) {
  131.         int bb = s[c + 1] == '+' ? 0 : 1;
  132.         tmp *= 10ll;
  133.         if (s[c] != '+' && (s[c] != '0' || c > j)) {
  134.             tmp += s[c] - '0';
  135.         }
  136.         else {
  137.             tmp += (c > j ? 0 : 1);
  138.             s[c] = (c > j ? '0' : '1');
  139.             cc++;
  140.         }
  141.         if (cc > q) break;
  142.         if (c == m - 2) continue;
  143.         if (c == m - 1) {
  144.             if (tmp <= mid && q >= cc && d[j][q] == tmp) {
  145.                 return;
  146.             }
  147.             int cnt = 0;
  148.             if (s[j] >= '2' && s[j] <= '9') {
  149.                 cnt = 1;
  150.                 tmp -= (s[j] - '1') * st[c - j];
  151.                 s[j] = '1';
  152.                 if (cnt + cc <= q && tmp <= mid && d[j][q] == tmp) return;
  153.             }
  154.             for (int e = j + 1; e <= c; e++) {
  155.                 if (s[e] == '0' || s[e] == '+') continue;
  156.                 cnt++;
  157.                 if (cnt + cc > q) break;
  158.                 tmp -= (s[e] - '0') * st[c - e];
  159.                 s[e] = '0';
  160.                 if (tmp <= mid && d[j][q] == tmp) {
  161.                     return;
  162.                 }
  163.             }
  164.             break;
  165.         }
  166.         if (cc + bb > q) continue;
  167.         if (tmp <= mid && d[j][q] == tmp + d[c + 2][q - bb - cc]) {
  168.             s[c + 1] = '+';
  169.             return void(vost(c + 2, q - bb - cc));
  170.         }
  171.         int cnt = 0;
  172.         auto tmp1 = tmp;
  173.         if (s[j] >= '2' && s[j] <= '9') {
  174.             cnt = 1;
  175.             tmp1 -= (s[j] - '1') * st[c - j];
  176.             if (cnt + bb + cc <= q && tmp1 <= mid && d[j][q] == tmp1 + d[c + 2][q - bb - cnt - cc]) {
  177.                 s[j] = '1';
  178.                 s[c + 1] = '+';
  179.                 return void(vost(c + 2, q - bb - cc - cnt));
  180.             }
  181.         }
  182.         for (int e = j + 1; e <= c; e++) {
  183.             if (s[e] == '0' || s[e] == '+') continue;
  184.             cnt++;
  185.             if (cnt + bb + cc > q) break;
  186.             tmp1 -= (s[e] - '0') * st[c - e];
  187.             if (tmp1 <= mid && d[j][q] == tmp1 + d[c + 2][q - bb - cnt - cc]) {
  188.                 s[j] = '1';
  189.                 for (int f = j + 1; f <= e; f++) s[f] = '0';
  190.                 s[c + 1] = '+';
  191.                 return void(vost(c + 2, q - bb - cnt - cc));
  192.             }
  193.         }
  194.     }
  195. }
  196. void find_ans() {
  197.     vost(0, k);
  198. }
  199. signed main() {
  200.     ios_base::sync_with_stdio(false);
  201.     cin.tie(nullptr);
  202.     cin >> m >> n >> k;
  203.     cin >> s;
  204.     int l = -1, r = n + 2;
  205.     while(r - l > 1) {
  206.         mid = (l + r) >> 1;
  207.         solve();
  208.         if (d[0][k] <= n) {
  209.             r = mid;
  210.         }
  211.         else {
  212.             l = mid;
  213.         }
  214.     }
  215.     if (r > n) cout << -1 << el;
  216.     else {
  217.         mid = r;
  218.         solve();
  219.         find_ans();
  220.         cout << s << el;
  221.     }
  222.     return 0;
  223. }
Add Comment
Please, Sign In to add comment