Submission #567735

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

copypaste3

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

char arr[2505];
int A,B,C;
int mem[2505][2505];

int cntocc(int a, int b, int st, int en){
    int cur = b;
    int ans = 1;
    while (cur+(b-a)<=en){
        bool can = true;
        for (int x = 0; x<b-a; x++){
            if (arr[cur+x]!=arr[a+x]){
                can = false;
                break;
            }
        }
        if (can){
            ans++;
            cur += b-a;
        }
        else{
            cur++;
        }
    }
    return ans;
}

int func(int a, int b){
    if (mem[a][b]!=-1) return mem[a][b];
    if (a==b) return 0;
    int ans = func(a+1,b)+A;
    for (int x = 1; x<b-a; x++){
        int 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);
    }
    //printf("func %lld %lld = %lld\n",a,b,ans);
    return mem[a][b] = ans;
}

main(){
    int n;
    scanf("%lld",&n);
    for (int x = 0; x<n; x++){
        scanf(" %c",&arr[x]);
    }
    scanf("%lld%lld%lld",&A,&B,&C);
    memset(mem,-1,sizeof(mem));
    printf("%lld",func(0,n));
}

Compilation message (stderr)

copypaste3.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main(){
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
copypaste3.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf(" %c",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~~
copypaste3.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     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