Submission #1017477

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;
using P = std::tuple<int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

std::string S;
int K;
const std::string INF(100, '9');
std::string dp[2000];

std::string bigger(const std::string& a, const std::string& b){
    if(a.size() > b.size()){return a;}
    else if(a.size() < b.size()){return b;}
    return a > b ? a : b;
}

std::string smaller(const std::string& a, const std::string& b){
    if(a.size() < b.size()){return a;}
    else if(a.size() > b.size()){return b;}
    return a < b ? a : b;
}

std::string solve800(){
    int S_size = S.size();
    int unitSize = S_size / K;
    int max_m = S_size % K, max_n = K - max_m;
    
    fill(dp, dp+2000, "-1");

    function<string(int,int,int)> loop = [&](int position, int n, int m) -> string{
        if(position == S_size){
            if(n == max_n && m == max_m){return "";}
            return INF;
        }

        if(dp[position] != "-1"){
            return dp[position];
        }

        dp[position] = INF;
        
        if(n < max_n && position + unitSize <= S_size){
            dp[position] = smaller(dp[position], bigger(S.substr(position, unitSize), loop(position + unitSize, n + 1, m)));
        }
        if(m < max_m && position + unitSize + 1 <= S_size){
            dp[position] = smaller(dp[position], bigger(S.substr(position, unitSize + 1), loop(position + unitSize + 1, n, m + 1)));
        }

        return dp[position];
    };

    return loop(0, 0, 0);
}

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    std::cin >> K;
    std::cin >> S;
    
    ++K;

    if(S.size() <= 2000){
        std::cout << solve800() << std::endl;
        return 0;
    }

    std::cout << "-1" << std::endl;
}

Submission Info

Judge Result