Submission #3878722

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <unordered_map>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

unordered_map<int,string>mp[100010];

string s;
int n;
int len;

string saiki(int x,int a){
    if(a<0)return "X";
    if(x>=n)return "&";
    if(a==0)return s.substr(x,n-x);
    if((len+1)*(a+1)<n-x)return "X";
    //if((len)*(a+1)>n-x)return "X";
    if(mp[x].find(a)!=mp[x].end())return mp[x][a];
    string p,q;
    if(x+len<n){
        string p1,p2;
        p1 = s.substr(x,len);
        p2 = saiki(x+len,a-1);
        if(p1=="X"){
            p = p1;
        }else if(p2=="X"){
            p = p2;
        }else if(p1.size()>p2.size()){
            p = p1;
        }else if(p1.size()<p2.size()){
            p = p2;
        }else{
            p = max(p1,p2);
        }
    }else{
        p = s.substr(x,n-x);
    }
    if(x+len+1>=n){
        q = s.substr(x,n-x);
    }else{
        string p1,p2;
        p1 = s.substr(x,len+1);
        p2 = saiki(x+len+1,a-1);
        if(p1=="X"){
            q = p1;
        }else if(p2=="X"){
            q = p2;
        }else if(p1.size()>p2.size()){
            q = p1;
        }else if(p1.size()<p2.size()){
            q = p2;
        }else{
            q = max(p1,p2);
        }
    }
    if(p=="X"){
        mp[x][a] = q;
    }else if(q=="X"){
        mp[x][a] = p;
    }else if(p.size()>q.size()){
        mp[x][a] = q;
    }else if(p.size()<q.size()){
        mp[x][a] = p;
    }else{
        mp[x][a] = min(p,q);
    }
    //cerr << x << " " << a << " "  << mp[x][a] << endl;
    return mp[x][a];
}

int main(){
    int k;
    cin >> k >> s;
    n = s.size();
    len = n/(k+1);
    //cerr << len << endl;
    cout << saiki(0,k) << endl;
    return 0;
}

Submission Info

Judge Result