#include #define all(v) v.begin(), v.end() #define prs(v) sort(all(v)); v.erase(unique(all(v)), v.end()) using namespace std; using ll = long long; using P = pair; int main(){ cin.tie(0)->sync_with_stdio(0); int n, w; cin >> n >> w; vector T(n); vector A(n + 1); for (auto &s : T) cin >> s; for (int s = 1; s <= n; s++) A[s] = T[s - 1].size(); int w_ = 0; vector ans; auto jud = [&] (int h,int op) { vector dp(n + 1, 1e9), cnt(n + 1); dp[0] = 0; for (int s = 1; s <= n; s++) { int mx = A[s]; for (int e = 1; e <= h; e++) { if (s - e < 0) break; if (dp[s] >= dp[s - e] + mx) { dp[s] = dp[s - e] + mx; cnt[s] = cnt[s - e] + 1; } mx = max(mx, A[s - e]); } } if (op) { w_ = cnt[n]; int cur = n; while (cur) { ans.push_back(cur); int nx = -1, mx = A[cur]; for (int e = 1; e <= h; e++) if (cur - e >= 0) { if (dp[cur - e] + mx == dp[cur]) { nx = cur - e; } mx = max(mx, A[cur - e]); } cur = nx; } } return dp[n] + cnt[n] - 1 <= w; }; int l = 0, r = n; while (l + 1 < r) { int m = (l + r) >> 1; (jud(m, 0) ? r : l) = m; } jud(r, 1); reverse(all(ans)); cout << r << " " << w_ << "\n"; int p = 1; vector> res; vector wid; for (int i : ans) { int mx = 0; res.emplace_back(); for (int s = p; s <= i; s++) { res.back().push_back(T[s - 1]); mx = max(mx, A[s]); } p = i + 1; wid.push_back(mx); cout << mx << " "; } cout << "\n"; for (int s = 0; s < r; s++) { for (int e = 0; e < w_; e++) { cout << left << setw(wid[e] + 1); if (s < res[e].size()) cout << res[e][s]; else cout << " "; } cout << "\n"; }; }

제출 #138808

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: