Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #ifdef ONLINE_JUDGE
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")
- #pragma GCC optimize("vpt")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
- #endif
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- const char el = '\n';
- const int inf = 1000'000'100;
- const ll llinf = 1e18, mod = 1000'000'007;
- const ld pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825;
- #define forn(i, n) for (int i = 0; i < (int)n; ++i)
- #define firn(i, n) for (int i = 1; i < (int)n; ++i)
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define x first
- #define y second
- #define debug(x) cout << #x << ": " << x << el
- template<typename T> bool uin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
- template<typename T> bool uax(T &a, T b) { if (b > a) { a = b; return 1; } return 0; }
- template<class iterator> void output(iterator begin, iterator end, char p = ' ', ostream & out = cout) { while (begin != end) { out << (*begin) << p; begin++; } out << el; }
- template<class T> void output(T x, char p = ' ', ostream & out = cout) { output(all(x), p, out); }
- mt19937 rnd(time(nullptr));
- #define int ll
- const int N = 301;
- int d[N][N], ans[N][N], d1[N][N][N];
- ll st[10] = {1ll, 10ll, 100ll, 1000ll, 10'000ll, 100'000ll, 1000'000ll, 10'000'000ll, 100'000'000ll, 1000'000'00'0ll};
- string s;
- int n, m, k, mid;
- void solve() {
- if ((int)s.size() == 1) {
- firn(j, k + 1) d[0][j] = 0;
- if (s[0] - '0' <= mid) d[0][0] = s[0] - '0';
- else d[0][0] = inf;
- }
- firn(j, k + 1) d[m - 1][j] = 0;
- assert(s.back() != '+');
- if (s.back() - '0' <= mid) d[m - 1][0] = s.back() - '0';
- else d[m - 1][0] = inf;
- for (int j = m - 2; j >= 0; j--) {
- forn(q, k + 1) {
- d[j][q] = inf;
- if (j < m - 2) {
- int tmp = (s[j] == '0' ? 0 : 1) + (s[j + 1] == '+' ? 0 : 1);
- if (q >= tmp) uin(d[j][q], d[j + 2][q - tmp]);
- }
- int cc = 0;
- ll tmp = 0;
- for (int c = j; c < m && c < j + 10; c++) {
- int bb = (s[c + 1] == '+' ? 0 : 1);
- tmp *= 10ll;
- if (s[c] != '+' && (s[c] != '0' || c > j)) {
- tmp += s[c] - '0';
- }
- else {
- tmp += (c > j ? 0 : 1);
- cc++;
- }
- if (cc > q) break;
- if (c == m - 2) continue;
- if (c == m - 1) {
- if (tmp <= mid && q >= cc)
- uin(d[j][q], (int)tmp);
- int cnt = 0;
- if (s[j] >= '2' && s[j] <= '9') {
- cnt = 1;
- tmp -= (s[j] - '1') * st[c - j];
- if (cnt + cc <= q && tmp <= mid) uin(d[j][q], (int)tmp);
- }
- for (int e = j + 1; e <= c; e++) {
- if (s[e] == '0' || s[e] == '+') continue;
- cnt++;
- if (cnt + cc > q) break;
- tmp -= (s[e] - '0') * st[c - e];
- if (tmp <= mid)
- uin(d[j][q], (int)tmp);
- }
- break;
- }
- if (cc + bb > q) continue;
- if (tmp <= mid)
- uin(d[j][q], (int)tmp + d[c + 2][q - cc - bb]);
- int cnt = 0;
- auto tmp1 = tmp;
- if (s[j] >= '2' && s[j] <= '9') {
- cnt = 1;
- tmp1 -= (s[j] - '1') * st[c - j];
- if (tmp1 <= mid && cnt + cc + bb <= q) uin(d[j][q], (int)tmp1 + d[c + 2][q - bb - cnt - cc]);
- }
- for (int e = j + 1; e <= c; e++) {
- if (s[e] == '0' || s[e] == '+') continue;
- cnt++;
- if (cnt + cc + bb > q) break;
- tmp1 -= (s[e] - '0') * st[c - e];
- if (tmp1 <= mid)
- uin(d[j][q], (int)tmp1 + d[c + 2][q - bb - cnt - cc]);
- }
- }
- }
- }
- }
- void vost(int j, int q) {
- if (j == m - 1) {
- if (q > 0) s[j] = '0';
- return;
- }
- if (j < m - 2) {
- int tmp = (s[j] == '0' ? 0 : 1) + (s[j + 1] == '+' ? 0 : 1);
- if (q >= tmp && d[j][q] == d[j + 2][q - tmp]) {
- s[j] = '0';
- s[j + 1] = '+';
- return void(vost(j + 2, q - tmp));
- }
- }
- int cc = 0;
- ll tmp = 0;
- for (int c = j; c < m; c++) {
- int bb = s[c + 1] == '+' ? 0 : 1;
- tmp *= 10ll;
- if (s[c] != '+' && (s[c] != '0' || c > j)) {
- tmp += s[c] - '0';
- }
- else {
- tmp += (c > j ? 0 : 1);
- s[c] = (c > j ? '0' : '1');
- cc++;
- }
- if (cc > q) break;
- if (c == m - 2) continue;
- if (c == m - 1) {
- if (tmp <= mid && q >= cc && d[j][q] == tmp) {
- return;
- }
- int cnt = 0;
- if (s[j] >= '2' && s[j] <= '9') {
- cnt = 1;
- tmp -= (s[j] - '1') * st[c - j];
- s[j] = '1';
- if (cnt + cc <= q && tmp <= mid && d[j][q] == tmp) return;
- }
- for (int e = j + 1; e <= c; e++) {
- if (s[e] == '0' || s[e] == '+') continue;
- cnt++;
- if (cnt + cc > q) break;
- tmp -= (s[e] - '0') * st[c - e];
- s[e] = '0';
- if (tmp <= mid && d[j][q] == tmp) {
- return;
- }
- }
- break;
- }
- if (cc + bb > q) continue;
- if (tmp <= mid && d[j][q] == tmp + d[c + 2][q - bb - cc]) {
- s[c + 1] = '+';
- return void(vost(c + 2, q - bb - cc));
- }
- int cnt = 0;
- auto tmp1 = tmp;
- if (s[j] >= '2' && s[j] <= '9') {
- cnt = 1;
- tmp1 -= (s[j] - '1') * st[c - j];
- if (cnt + bb + cc <= q && tmp1 <= mid && d[j][q] == tmp1 + d[c + 2][q - bb - cnt - cc]) {
- s[j] = '1';
- s[c + 1] = '+';
- return void(vost(c + 2, q - bb - cc - cnt));
- }
- }
- for (int e = j + 1; e <= c; e++) {
- if (s[e] == '0' || s[e] == '+') continue;
- cnt++;
- if (cnt + bb + cc > q) break;
- tmp1 -= (s[e] - '0') * st[c - e];
- if (tmp1 <= mid && d[j][q] == tmp1 + d[c + 2][q - bb - cnt - cc]) {
- s[j] = '1';
- for (int f = j + 1; f <= e; f++) s[f] = '0';
- s[c + 1] = '+';
- return void(vost(c + 2, q - bb - cnt - cc));
- }
- }
- }
- }
- void find_ans() {
- vost(0, k);
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> m >> n >> k;
- cin >> s;
- int l = -1, r = n + 2;
- while(r - l > 1) {
- mid = (l + r) >> 1;
- solve();
- if (d[0][k] <= n) {
- r = mid;
- }
- else {
- l = mid;
- }
- }
- if (r > n) cout << -1 << el;
- else {
- mid = r;
- solve();
- find_ans();
- cout << s << el;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment