Submission #3772220

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 2000;
const int K = 10000;

string s[N];
bitset<K + 1> bs[N + 20];
int nv[2];
pair<int, int> v[2][N + 20];

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

Submission Info

Judge Result