Submission #3772180

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  vector<bitset<10001>> bs(n + 1);
  bs[n].set(k);
  vector<vector<pair<int, int>>> v(2);
  for (int i = n - 1; i >= 0; --i) {
    int sz = (int) s[i].size();
    bs[i] = bs[i + 1] | (bs[i + 1] >> sz);
    if (bs[i + 1][sz]) {
      v[0].emplace_back(i, 0);
    }
  }
  string ans = "";
  for (int i = 0; i < k; ++i) {
    int iter = i & 1;
    char c = 'z';
    for (const auto& p : v[iter]) {
      c = min(c, s[p.first][p.second]);
    }
    ans += c;
    int bid = n;
    for (const auto& p : v[iter]) {
      int id, j;
      tie(id, j) = p;
      if (s[id][j] != c) {
        continue;
      }
      if (j == (int) s[id].size() - 1) {
        bid = min(bid, id);
      } else {
        v[iter ^ 1].emplace_back(id, j + 1);
      }
    }
    for (int j = bid + 1; j < n; ++j) {
      if (i + 1 + (int) s[j].size() <= k && bs[j + 1][i + 1 + (int) s[j].size()]) {
        v[iter ^ 1].emplace_back(j, 0);
      }
    }
    v[iter].clear();
  }
  cout << ans << '\n';
  return 0;
}

Submission Info

Judge Result