Submission #770341

#	Time	Username	Problem	Language	Result	Execution time	Memory
770341		Amylopectin	Copy and Paste 3 (JOI22_copypaste3)	C++14	5 / 100	3 ms	320 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;
        cou = n/i;
        cmi = re(0,i-1) + c2 + cou * c3 + c1 * (n-cou*i);
                    if(fmi > cmi)
                    {
                        fmi = cmi;
                    }
        // 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+i-1;
        //         for(k=j+i-1; 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+i-1;
        //         for(k=j+i-1; 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(cr-k < i)
        //                     break;
        //             }
        //         }
        //         // 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:17: warning: unused variable 'j' [-Wunused-variable]
   16 |     long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
      |                 ^
copypaste3.cpp:16:19: warning: unused variable 'k' [-Wunused-variable]
   16 |     long long i,j,k,o,n = cr - cl + 1,cn,cm,cou,cma = 1,fmi = -1,cmi;
      |                   ^
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:39: warning: unused variable 'cn' [-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:127:18: warning: format '%s' expects argument of type 'char*', but argument 3 has type 'char (*)[3010]' [-Wformat=]
  127 |     scanf("%lld %s %lld %lld %lld",&n,&s,&c1,&c2,&c3);
      |                 ~^                    ~~
      |                  |                    |
      |                  char*                char (*)[3010]
copypaste3.cpp:126:15: warning: unused variable 'i' [-Wunused-variable]
  126 |     long long i,j,m,n;
      |               ^
copypaste3.cpp:126:17: warning: unused variable 'j' [-Wunused-variable]
  126 |     long long i,j,m,n;
      |                 ^
copypaste3.cpp:126:19: warning: unused variable 'm' [-Wunused-variable]
  126 |     long long i,j,m,n;
      |                   ^
copypaste3.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%lld %s %lld %lld %lld",&n,&s,&c1,&c2,&c3);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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