Submission #1017472


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[100][110];

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 solve400(){
    int S_size = S.size();
    int unitSize = S_size / K;

    fill(&dp[0][0], &dp[0][0]+100*110, "-1");
    
    std::function<std::string(int,int)> loop = [&](int position, int n) -> std::string{
        if(position == S_size || n == K){
            if(position == S_size && n == K){
                return "";
            }

            return INF;
        }

        if(dp[position][n] != "-1"){
            return dp[position][n];
        }
        
        std::string s1 = position + unitSize > S_size ? INF : bigger(S.substr(position, unitSize), loop(position + unitSize, n + 1)),
        s2 = position + unitSize + 1 > S_size ? INF : bigger(S.substr(position, unitSize + 1), loop(position + unitSize + 1, n + 1));

        return dp[position][n] = smaller(s1, s2);
    };

    return loop(0, 0);
}

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

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

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

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

Submission Info

Submission Time
Task B - Problem where Commas Separate Digits
User iwashisnake
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1884 Byte
Status WA
Exec Time 4 ms
Memory 896 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3 Dataset4 Dataset5
Score / Max Score 0 / 0 100 / 100 100 / 100 200 / 200 0 / 200 0 / 400
Status
AC × 3
AC × 17
AC × 32
AC × 49
AC × 49
WA × 15
AC × 49
WA × 30
Set Name Test Cases
Sample subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset1 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt
Dataset2 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt
Dataset3 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt
Dataset4 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt
Dataset5 subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 4 ms 896 KB
subtask_01_02.txt AC 4 ms 896 KB
subtask_01_03.txt AC 4 ms 896 KB
subtask_01_04.txt AC 4 ms 896 KB
subtask_01_05.txt AC 4 ms 896 KB
subtask_01_06.txt AC 4 ms 896 KB
subtask_01_07.txt AC 4 ms 896 KB
subtask_01_08.txt AC 4 ms 896 KB
subtask_01_09.txt AC 4 ms 896 KB
subtask_01_10.txt AC 4 ms 896 KB
subtask_01_11.txt AC 4 ms 896 KB
subtask_01_12.txt AC 4 ms 896 KB
subtask_01_13.txt AC 4 ms 896 KB
subtask_01_14.txt AC 4 ms 896 KB
subtask_01_15.txt AC 4 ms 896 KB
subtask_01_16.txt AC 4 ms 896 KB
subtask_01_17.txt AC 4 ms 896 KB
subtask_02_01.txt AC 4 ms 896 KB
subtask_02_02.txt AC 4 ms 896 KB
subtask_02_03.txt AC 4 ms 896 KB
subtask_02_04.txt AC 4 ms 896 KB
subtask_02_05.txt AC 4 ms 896 KB
subtask_02_06.txt AC 4 ms 896 KB
subtask_02_07.txt AC 4 ms 896 KB
subtask_02_08.txt AC 4 ms 896 KB
subtask_02_09.txt AC 4 ms 896 KB
subtask_02_10.txt AC 4 ms 896 KB
subtask_02_11.txt AC 4 ms 896 KB
subtask_02_12.txt AC 4 ms 896 KB
subtask_02_13.txt AC 4 ms 896 KB
subtask_02_14.txt AC 4 ms 896 KB
subtask_02_ex1.txt AC 4 ms 896 KB
subtask_03_01.txt AC 4 ms 896 KB
subtask_03_02.txt AC 4 ms 896 KB
subtask_03_03.txt AC 4 ms 896 KB
subtask_03_04.txt AC 4 ms 896 KB
subtask_03_05.txt AC 4 ms 896 KB
subtask_03_06.txt AC 4 ms 896 KB
subtask_03_07.txt AC 4 ms 896 KB
subtask_03_08.txt AC 4 ms 896 KB
subtask_03_09.txt AC 4 ms 896 KB
subtask_03_10.txt AC 4 ms 896 KB
subtask_03_11.txt AC 4 ms 896 KB
subtask_03_12.txt AC 4 ms 896 KB
subtask_03_13.txt AC 4 ms 896 KB
subtask_03_14.txt AC 4 ms 896 KB
subtask_03_15.txt AC 4 ms 896 KB
subtask_03_ex2.txt AC 4 ms 896 KB
subtask_03_ex3.txt AC 4 ms 896 KB
subtask_04_01.txt WA 3 ms 384 KB
subtask_04_02.txt WA 3 ms 384 KB
subtask_04_03.txt WA 3 ms 384 KB
subtask_04_04.txt WA 3 ms 384 KB
subtask_04_05.txt WA 3 ms 384 KB
subtask_04_06.txt WA 3 ms 384 KB
subtask_04_07.txt WA 3 ms 384 KB
subtask_04_08.txt WA 3 ms 384 KB
subtask_04_09.txt WA 3 ms 384 KB
subtask_04_10.txt WA 3 ms 384 KB
subtask_04_11.txt WA 3 ms 384 KB
subtask_04_12.txt WA 3 ms 384 KB
subtask_04_13.txt WA 3 ms 384 KB
subtask_04_14.txt WA 3 ms 384 KB
subtask_04_15.txt WA 3 ms 384 KB
subtask_05_01.txt WA 3 ms 640 KB
subtask_05_02.txt WA 3 ms 640 KB
subtask_05_03.txt WA 3 ms 640 KB
subtask_05_04.txt WA 3 ms 640 KB
subtask_05_05.txt WA 3 ms 640 KB
subtask_05_06.txt WA 3 ms 640 KB
subtask_05_07.txt WA 3 ms 640 KB
subtask_05_08.txt WA 3 ms 640 KB
subtask_05_09.txt WA 3 ms 640 KB
subtask_05_10.txt WA 3 ms 640 KB
subtask_05_11.txt WA 3 ms 640 KB
subtask_05_12.txt WA 3 ms 640 KB
subtask_05_13.txt WA 3 ms 512 KB
subtask_05_14.txt WA 3 ms 512 KB
subtask_05_15.txt WA 3 ms 384 KB