oj.uz

Submission #770341

# Submission time Handle Problem Language Result Execution time Memory
770341 2023-07-01T05:47:54 Z Amylopectin Copy and Paste 3 (JOI22_copypaste3) C++14
5 / 100
 3 ms 320 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 320 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 308 KB Output is correct
8 Correct 3 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 304 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -