110252024-06-17 11:49:20mraron2016. januárcpp17Accepted 702ms1016 KiB
#include<bits/stdc++.h>
using namespace std;

struct node {
    int child[3];
    int par, par_c;
    int go[3]={-1,-1,-1};
    int link=-1;
    
    bool ends;
    int sum_on_links=-1;
};

node aho[10100];
int nxt=1;

void add(string& s) {
    int curr=0;
    for(char c:s) {
        if(!aho[curr].child[c-'0']) {
            aho[curr].child[c-'0']=nxt++;
            aho[aho[curr].child[c-'0']].par=curr;
            aho[aho[curr].child[c-'0']].par_c=c-'0';
        }
        curr=aho[curr].child[c-'0'];
    }
    aho[curr].ends=true;
}

int go(int x, int c);
int get_link(int x) {
    if(aho[x].link!=-1) return aho[x].link;
    if(!x || !aho[x].par) return aho[x].link=0;
    return aho[x].link=go(get_link(aho[x].par), aho[x].par_c);
}
int go(int x, int c) {
    if(aho[x].go[c]!=-1) return aho[x].go[c];
    if(aho[x].child[c]>0) return aho[x].go[c]=aho[x].child[c];
    if(x==0) return aho[x].go[c]=0;
    if(get_link(x)!=x) {
        return aho[x].go[c]=go(get_link(x), c);
    }
    return aho[x].go[c]=0;
}

int sum(int x) {
    if(x==0) return 0;
    if(aho[x].sum_on_links!=-1) return aho[x].sum_on_links;
    return aho[x].sum_on_links=(int)aho[x].ends+sum(get_link(x));
}



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n,k;
    cin>>n>>k;
    assert(k<=5000);
    int sum_len=0;
    for(int i=0;i<n;++i) {
        string s;
        cin>>s;
        add(s);
        assert((sum_len+=s.size())<=10000);
    }
    for(int i=0;i<nxt;++i) {
        sum(i);
    }
    vector<int> dp(nxt,-1e9);
    dp[0]=0;
    for(int i=0;i<k;++i) {
        vector<int> ndp(nxt, -1e9);
        for(int j=0;j<nxt;++j) {
            for(int c=0;c<3;++c) {
                int st=go(j, c);
                ndp[st]=max(ndp[st], aho[st].sum_on_links+dp[j]);
            }
        }
        ndp.swap(dp);
    }
    cout<<*max_element(dp.begin(), dp.end())<<"\n";
}
1 - Accepted
Memory: 868KiB
Time: 3ms

Program's output:
99
Expected output:
99
Checker output:

2 - Accepted
Memory: 868KiB
Time: 3ms

Program's output:
1999
Expected output:
1999
Checker output:

3 - Accepted
Memory: 868KiB
Time: 4ms

Program's output:
11249
Expected output:
11249
Checker output:

4 - Accepted
Memory: 868KiB
Time: 3ms

Program's output:
322
Expected output:
322
Checker output:

5 - Accepted
Memory: 868KiB
Time: 3ms

Program's output:
491
Expected output:
491
Checker output:

6 - Accepted
Memory: 872KiB
Time: 85ms

Program's output:
31308
Expected output:
31308
Checker output:

7 - Accepted
Memory: 868KiB
Time: 296ms

Program's output:
19994
Expected output:
19994
Checker output:

8 - Accepted
Memory: 772KiB
Time: 405ms

Program's output:
12999
Expected output:
12999
Checker output:

9 - Accepted
Memory: 776KiB
Time: 391ms

Program's output:
14996
Expected output:
14996
Checker output:

10 - Accepted
Memory: 868KiB
Time: 388ms

Program's output:
71
Expected output:
71
Checker output:

11 - Accepted
Memory: 868KiB
Time: 391ms

Program's output:
54
Expected output:
54
Checker output:

12 - Accepted
Memory: 868KiB
Time: 3ms

Program's output:
221
Expected output:
221
Checker output:

13 - Accepted
Memory: 888KiB
Time: 14ms

Program's output:
690270
Expected output:
690270
Checker output:

14 - Accepted
Memory: 1016KiB
Time: 231ms

Program's output:
390910
Expected output:
390910
Checker output:

15 - Accepted
Memory: 868KiB
Time: 37ms

Program's output:
675595
Expected output:
675595
Checker output:

16 - Accepted
Memory: 868KiB
Time: 314ms

Program's output:
267074
Expected output:
267074
Checker output:

17 - Accepted
Memory: 936KiB
Time: 584ms

Program's output:
64749
Expected output:
64749
Checker output:

18 - Accepted
Memory: 868KiB
Time: 702ms

Program's output:
14997
Expected output:
14997
Checker output: