Submission #857193


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string w;
    cin>>w;
    int n = (int)w.length();

    vector<vector<int>> P(n+1);
    for (int i=1; i<=n; i++)
        for (int j=1; j<i; j++)
            if (i%j==0)
                P[i].push_back(j);
    
    vector<vector<bool>> G(n, vector<bool>(n, true));

    for (int s=0; s<n; s++)
    for (int t=s; t<n; t++)
    {
        for (int p: P[t-s+1])
        {
            bool f = true;
            for (int i=s+p; i<=t && G[s][t]; i++)
                if (w[i] != w[i-p])
                    f = false;
            if (f)
                G[s][t] = false;
            if (!G[s][t])
                break;
        }
    }

    vector<long long> A(n);
    vector<long long> B(n, n);

    for (int i=0; i<n; i++)
    {
        if (G[0][i])
            B[i] = 1,
            A[i] = 1;
        for (int j=0; j<i; j++)
        if (G[j+1][i])
        {
            long long t = B[j]+1;
            if (t<B[i])
                B[i] = t,
                A[i] = 0;
            if (t==B[i])
                A[i] += A[j],
                A[i] %= 1000000007;
        }
    }

    cout<<B[n-1]<<endl;
    cout<<A[n-1]<<endl;
}

Submission Info

Submission Time
Task F - Best Representation
User kusano
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1276 Byte
Status TLE
Exec Time 2144 ms
Memory 13956 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 400 0 / 500
Status
AC × 3
AC × 10
TLE × 26
AC × 10
TLE × 55
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt
All example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
example_02.txt AC 4 ms 256 KB
example_03.txt AC 4 ms 256 KB
subtask1_01.txt AC 4 ms 256 KB
subtask1_02.txt AC 4 ms 256 KB
subtask1_03.txt AC 1199 ms 384 KB
subtask1_04.txt TLE 2101 ms 2688 KB
subtask1_05.txt TLE 2101 ms 2688 KB
subtask1_06.txt TLE 2101 ms 2688 KB
subtask1_07.txt TLE 2101 ms 2688 KB
subtask1_08.txt TLE 2105 ms 2688 KB
subtask1_09.txt TLE 2101 ms 2688 KB
subtask1_10.txt TLE 2101 ms 2688 KB
subtask1_11.txt TLE 2122 ms 2688 KB
subtask1_12.txt TLE 2101 ms 2688 KB
subtask1_13.txt TLE 2117 ms 2688 KB
subtask1_14.txt TLE 2105 ms 2688 KB
subtask1_15.txt AC 4 ms 256 KB
subtask1_16.txt AC 4 ms 256 KB
subtask1_17.txt AC 4 ms 256 KB
subtask1_18.txt AC 4 ms 256 KB
subtask1_19.txt TLE 2101 ms 2688 KB
subtask1_20.txt TLE 2101 ms 2688 KB
subtask1_21.txt TLE 2105 ms 2688 KB
subtask1_22.txt TLE 2126 ms 2688 KB
subtask1_23.txt TLE 2101 ms 2688 KB
subtask1_24.txt TLE 2101 ms 2688 KB
subtask1_25.txt TLE 2101 ms 2688 KB
subtask1_26.txt TLE 2105 ms 2688 KB
subtask1_27.txt TLE 2105 ms 2688 KB
subtask1_28.txt TLE 2105 ms 2688 KB
subtask1_29.txt TLE 2101 ms 2688 KB
subtask1_30.txt TLE 2105 ms 2560 KB
subtask1_31.txt TLE 2101 ms 2688 KB
subtask1_32.txt TLE 2102 ms 2688 KB
subtask1_33.txt TLE 2105 ms 2688 KB
subtask2_01.txt TLE 2106 ms 11268 KB
subtask2_02.txt TLE 2102 ms 13828 KB
subtask2_03.txt TLE 2102 ms 13828 KB
subtask2_04.txt TLE 2106 ms 13828 KB
subtask2_05.txt TLE 2102 ms 13956 KB
subtask2_06.txt TLE 2102 ms 13956 KB
subtask2_07.txt TLE 2102 ms 13956 KB
subtask2_08.txt TLE 2106 ms 13956 KB
subtask2_09.txt TLE 2106 ms 13956 KB
subtask2_10.txt TLE 2102 ms 13956 KB
subtask2_11.txt TLE 2106 ms 13956 KB
subtask2_12.txt TLE 2106 ms 13956 KB
subtask2_13.txt TLE 2106 ms 13956 KB
subtask2_14.txt TLE 2106 ms 13956 KB
subtask2_15.txt TLE 2102 ms 13956 KB
subtask2_16.txt TLE 2102 ms 13956 KB
subtask2_17.txt TLE 2103 ms 13956 KB
subtask2_18.txt TLE 2106 ms 13956 KB
subtask2_19.txt TLE 2102 ms 13956 KB
subtask2_20.txt TLE 2144 ms 13956 KB
subtask2_21.txt TLE 2106 ms 13060 KB
subtask2_22.txt TLE 2102 ms 13956 KB
subtask2_23.txt TLE 2127 ms 13956 KB
subtask2_24.txt TLE 2102 ms 12036 KB
subtask2_25.txt TLE 2102 ms 12548 KB
subtask2_26.txt TLE 2102 ms 13316 KB
subtask2_27.txt TLE 2102 ms 11652 KB
subtask2_28.txt TLE 2106 ms 8068 KB
subtask2_29.txt TLE 2102 ms 11268 KB