Submission #770301

#	Time	Username	Problem	Language	Result	Execution time	Memory
770301		Amylopectin	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	3031 ms	2568 KiB

copypaste3

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
const long long mxn = 3e3 + 10;
// const long long mxn = 20;
char s[mxn] = {};
long long c1,c2,c3,u[mxn] = {},rev[mxn] = {},dp[mxn][mxn] = {};
long long re(long long cl,long long cr)
{
    if(dp[cl][cr] != 0)
    {
        return dp[cl][cr];
    }
    long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
    for(i=cl; i<=cr; i++)
    {
        u[i] = 0;
    }
    fmi = c1 * n;
    for(i=n/2; i>0; i--)
    {
        cma = 1;
        for(j=cl; j<=cl+n - i*2; j++)
        {
            if(u[j] != i)
            {
                cou = 0;
                cn = j;
                rev[j] = j;
                for(k=j+1; k<j+i; k++)
                {
                    while(1)
                    {
                        if(s[k] == s[cn])
                        {
                            rev[k] = cn+1;
                            cn++;
                            break;
                        }
                        if(cn == j)
                        {
                            rev[k] = j;
                            break;
                        }
                        cn = rev[cn-1];
                    }
                }
                cn = j;
                for(k=j; k<=cr; k++)
                {
                    while(1)
                    {
                        if(s[k] == s[cn])
                        {
                            cn++;
                            break;
                        }
                        if(cn == j)
                        {
                            break;
                        }
                        cn = rev[cn-1];
                    }
                    if(cn == j+i)
                    {
                        u[k-i+1] = i;
                        cn = rev[cn-1];
                    }
                }
                cn = j;
                for(k=j; k<=cr; k++)
                {
                    while(1)
                    {
                        if(s[k] == s[cn])
                        {
                            cn++;
                            break;
                        }
                        if(cn == j)
                        {
                            break;
                        }
                        cn = rev[cn-1];
                    }
                    if(cn == j+i)
                    {
                        cou ++;
                        cn = j;
                    }
                }
                // if(fmi == -1)
                // {
                //     fmi = re(j,j+i-1) + c2 + cou * c3 + c1 * (n-cou*i);
                // }
                // else 
                // {
                    cmi = re(j,j+i-1) + c2 + cou * c3 + c1 * (n-cou*i);
                    if(fmi > cmi)
                    {
                        fmi = cmi;
                    }
                // }
                // if(cou > cma)
                // {
                //     cma = cou;
                // }
            }
        }
    }
    dp[cl][cr] = fmi;
    return fmi;
}
int main()
{
    long long i,j,m,n;
    scanf("%lld %s %lld %lld %lld",&n,&s,&c1,&c2,&c3);
    re(0,n-1);
    printf("%lld",dp[0][n-1]);
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'long long int re(long long int, long long int)':
copypaste3.cpp:16:21: warning: unused variable 'o' [-Wunused-variable]
   16 |     long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
      |                     ^
copypaste3.cpp:16:42: warning: unused variable 'cm' [-Wunused-variable]
   16 |     long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
      |                                          ^~
copypaste3.cpp:16:49: warning: variable 'cma' set but not used [-Wunused-but-set-variable]
   16 |     long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
      |                                                 ^~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:119:18: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[3010]' [-Wformat=]
  119 |     scanf("%lld %s %lld %lld %lld",&n,&s,&c1,&c2,&c3);
      |                 ~^                    ~~
      |                  |                    |
      |                  char*                char (*)[3010]
copypaste3.cpp:118:15: warning: unused variable 'i' [-Wunused-variable]
  118 |     long long i,j,m,n;
      |               ^
copypaste3.cpp:118:17: warning: unused variable 'j' [-Wunused-variable]
  118 |     long long i,j,m,n;
      |                 ^
copypaste3.cpp:118:19: warning: unused variable 'm' [-Wunused-variable]
  118 |     long long i,j,m,n;
      |                   ^
copypaste3.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%lld %s %lld %lld %lld",&n,&s,&c1,&c2,&c3);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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