Insert Whitespace

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
 
pair<int, int> dp[5005][52][82];
 
int n,h,w,p;
int tw=0;
 
string www[5005];
int par[5005];
 
string spas(int x){
    string r;
    for (int i=0;i<x;i++){
        r+=' ';
    }
    return r;
}
 
pair<pair<int, int>, string> ns(int i, int l, int ch, int sp){
    if (i==tw-1){ // kaikki loppu
        if (l==0) return {{-1, -1}, ""};
        if (ch+(int)www[i].size()<=w){
            return {{l, ch+(int)www[i].size()}, www[i]};
        } else {
            return {{-1, -1}, ""};
        }
    } else if (par[i] != par[i+1]) { // paragraph loppu
        if (l==0) return {{-1, -1}, ""};
        if (l==h-2) return {{-1, -1}, ""};
        if (ch+(int)www[i].size()<=w){
            if (l==h-1){
                return {{0, p}, www[i]+"\n#\n"+spas(p)};
            } else{
                return {{l+1, p}, www[i]+"\n"+spas(p)};
            }
        }
    } else if (ch+(int)www[i].size()==w){ // rivi loppu
        if (l==h-1){
            return {{0, 0}, www[i]+"\n#\n"};
        } else {
            return {{l+1, 0}, www[i]+"\n"};
        }
    } else if (ch+sp+(int)www[i].size()<w) { // rivi ei lopu
        return {{l, ch+sp+(int)www[i].size()}, www[i]+spas(sp)};
    } else {
        return {{-1, -1}, ""};
    }
    return {{-1, -1}, ""};
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>h>>w>>p;
    string temp;
    getline(cin, temp);
    for (int i=0;i<n;i++){
        getline(cin, temp);
        stringstream ss;
        ss<<temp;
        while (ss>>temp){
            par[tw]=i;
            www[tw++]=temp;
        }
    }
    for (int i=0;i<=tw;i++){
        for (int j=0;j<=h;j++){
            for (int k=0;k<=w;k++){
                dp[i][j][k]={-1, -1};
            }
        }
    }
    const pair<int, int> fail={-1, -1};
    dp[0][0][p]={0, 0};
    for (int i=0;i<tw;i++){
        for (int j=0;j<h;j++){
            for (int x=0;x<=w;x++){
                if (dp[i][j][x]==fail) continue;
                for (int a=1;a<=2;a++){
                    auto ne=ns(i, j, x, a);
                    if (ne.F==fail) continue;
                    dp[i+1][ne.F.F][ne.F.S]={j, x};
                }
            }
        }
    }
    pair<int, int> rec=fail;
    for (int j=0;j<h;j++){
        for (int x=0;x<=w;x++){
            if (dp[tw][j][x]!=fail) {
                rec={j, x};
            }
        }
    }
    if (rec==fail){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    vector<string> ans;
    for (int i=tw;i>0;i--){
        auto from=dp[i][rec.F][rec.S];
        int f=0;
        for (int a=1;a<=2;a++){
            auto lol=ns(i-1, from.F, from.S, a);
            if (lol.F==rec){
                ans.push_back(lol.S);
                rec=from;
                f=1;
                break;
            }
        }
        assert(f);
    }
    cout<<spas(p);
    for (int i=(int)ans.size()-1;i>=0;i--){
        cout<<ans[i];
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED