Submission #567799

#	Time	Username	Problem	Language	Result	Execution time	Memory
567799		tqbfjotld	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	3071 ms	100860 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;

char arr[2505];
long long A,B,C;
long long mem[2505*1305];
int ct = 1;

struct node{
    int nid;
    short len;
    vector<short> vals;
    node*ch[26];
    vector<vector<short> >decomp;
    node(int _len){
        nid = ct++;
        len = _len;
        for (int x = 0; x<26; x++){
            ch[x] = 0;
        }
    }
    void construct(){
        //printf("call construct len %lld\n",len);
        int lgx = 1;
        while ((1<<(lgx))<=vals.size()) lgx++;
        decomp.resize(lgx);
        for (int x = 0; x<vals.size(); x++){
            decomp[0].push_back(lower_bound(vals.begin(),vals.end(),vals[x]+len)-vals.begin());
        }
        decomp[0].push_back(vals.size());
        for (int x = 1; x<decomp.size(); x++){
            for (int y = 0; y<=vals.size(); y++){
                decomp[x].push_back(decomp[x-1][decomp[x-1][y]]);
            }
        }
    }
    void constructall(){
        construct();
        for (int x = 0; x<26; x++){
            if (ch[x]!=0){
                ch[x]->constructall();
            }
        }
    }
    int cntocc(int st, int en){
        //printf("call cntocc %lld %lld, len %lld\n",st,en,len);
        int cur = lower_bound(vals.begin(),vals.end(),st)-vals.begin();
        int ans = 1;
        int r = upper_bound(vals.begin(),vals.end(),en-len)-vals.begin();
        for (int x = (int)decomp.size()-1; x>=0; x--){
            if (decomp[x][cur]<r){
                ans += (1<<x);
                cur = decomp[x][cur];
            }
        }
        return ans;
    }
}*rt;

node* pt[2505][2505];

inline int cntocc(int a, int b, int st, int en){
    return pt[a][b]->cntocc(st,en);
}

/*
long long func(int a, int b){
    if (a==b) return 0;
    if (mem[pt[a][b]->nid]!=-1) return mem[pt[a][b]->nid];
    long long ans = func(a+1,b)+A;
    for (int x = 1; x<b-a; x++){
        long long t = func(a,a+x);
        int t2 = cntocc(a,a+x,a,b);
        ans = min(ans,t+B+t2*C+(b-a-x*t2)*A);
        if (t2==1) break;
    }
    //printf("func %lld %lld = %lld\n",a,b,ans);
    return mem[pt[a][b]->nid] = ans;
}
*/

main(){
    int n;
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf(" %c",&arr[x]);
    }
    scanf("%lld%lld%lld",&A,&B,&C);
    memset(mem,-1,sizeof(mem));
    for (int x = 0; x<n; x++){
        if (rt==0){
            rt = new node(0);
        }
        node *cur = rt;
        pt[x][x] = rt;
        for (int y = x+1; y<=n; y++){
            if (cur->ch[arr[y-1]-'a']==0){
                cur->ch[arr[y-1]-'a'] = new node(y-x);
            }
            cur = cur->ch[arr[y-1]-'a'];
            cur->vals.push_back(x);
            pt[x][y] = cur;
        }
    }
    pt[n][n] = rt;
    rt->constructall();
    mem[rt->nid] = 0;
    for (int x = 1; x<=n; x++){
        for (int y = 0; x+y<=n; y++){
            int a = y;
            int b = x+y;
            //printf("a b %d %d\n",a,b);
            long long ans = mem[pt[a+1][b]->nid]+A;
            for (int x = 1; x<b-a; x++){
                long long t = mem[pt[a][a+x]->nid];
                int t2 = cntocc(a,a+x,a,b);
                ans = min(ans,t+B+t2*C+(b-a-x*t2)*A);
                if (t2==1) break;
            }
            //printf("func %lld %lld = %lld\n",a,b,ans);
            mem[pt[a][b]->nid] = ans;
        }
    }
    printf("%lld",mem[pt[0][n]->nid]);
}

Compilation message (stderr)

copypaste3.cpp: In member function 'void node::construct()':
copypaste3.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while ((1<<(lgx))<=vals.size()) lgx++;
      |                ~~~~~~~~~~^~~~~~~~~~~~~
copypaste3.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int x = 0; x<vals.size(); x++){
      |                         ~^~~~~~~~~~~~
copypaste3.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int x = 1; x<decomp.size(); x++){
      |                         ~^~~~~~~~~~~~~~
copypaste3.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int y = 0; y<=vals.size(); y++){
      |                             ~^~~~~~~~~~~~~
copypaste3.cpp: At global scope:
copypaste3.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
copypaste3.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf(" %c",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~
copypaste3.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%lld%lld%lld",&A,&B,&C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38