oj.uz

Submission #895998

# Submission time Handle Problem Language Result Execution time Memory
895998 2023-12-31T11:49:55 Z alexander707070 Copy and Paste 3 (JOI22_copypaste3) C++14
15 / 100
 1281 ms 451692 KB 
#include<bits/stdc++.h>
#define MAXN 37
using namespace std;

const long long inf=1e15;
const long long mod=1000000000100011;

int n;
long long a,b,c;
char s[MAXN];

long long dp[MAXN][MAXN][MAXN][MAXN][2*MAXN];
bool li[MAXN][MAXN][MAXN][MAXN][2*MAXN];

long long hesh(int l,int r){
    long long res=0;
    for(int i=l;i<=r;i++){
        res*=26; res+=s[i]-'a';
        res%=mod;
    }
    return res;
}

long long ff(int l,int r,int ll,int rr,int step){
    if(step>2*n)return inf;
    if(l==1 and r==n)return 0;

    if(li[l][r][ll][rr][step])return dp[l][r][ll][rr][step];
    li[l][r][ll][rr][step]=true;
    dp[l][r][ll][rr][step]=inf;

    if(l==0 and r==0){
        dp[l][r][ll][rr][step]=ff(ll,rr,ll,rr,step+1)+c;
        for(int i=1;i<=n;i++){
            dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(i,i,ll,rr,step+1)+a);
        }
        return dp[l][r][ll][rr][step];
    }

    dp[l][r][ll][rr][step]=ff(0,0,l,r,step+1)+b;

    if(r<n){
        dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(l,r+1,ll,rr,step+1)+a);
    }

    if(ll!=0 and r+(rr-ll+1)<=n and hesh(ll,rr)==hesh(r+1,r+(rr-ll+1))){
        dp[l][r][ll][rr][step]=min(dp[l][r][ll][rr][step],ff(l,r+(rr-ll+1),ll,rr,step+1)+c);
    }

    return dp[l][r][ll][rr][step];
}

int main(){

    cin>>n>>(s+1);
    cin>>a>>b>>c;

    cout<<ff(0,0,0,0,0)<<"\n";

    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 140192 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Runtime error 22 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 11 ms 74496 KB Output is correct
12 Correct 35 ms 140380 KB Output is correct
13 Correct 60 ms 175876 KB Output is correct
14 Correct 6 ms 44376 KB Output is correct
15 Correct 63 ms 193692 KB Output is correct
16 Correct 13 ms 85336 KB Output is correct
17 Correct 4 ms 27480 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 17 ms 98396 KB Output is correct
20 Correct 2 ms 19036 KB Output is correct
21 Correct 1281 ms 426052 KB Output is correct
22 Correct 890 ms 451692 KB Output is correct
23 Correct 865 ms 450984 KB Output is correct
24 Correct 845 ms 451000 KB Output is correct
25 Correct 842 ms 448408 KB Output is correct
26 Correct 850 ms 448572 KB Output is correct
27 Correct 1004 ms 444824 KB Output is correct
28 Correct 1041 ms 447208 KB Output is correct
29 Correct 902 ms 447356 KB Output is correct
30 Correct 943 ms 449144 KB Output is correct
31 Correct 895 ms 448132 KB Output is correct
32 Correct 897 ms 447020 KB Output is correct
33 Correct 840 ms 446060 KB Output is correct
34 Correct 1 ms 2392 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 3 ms 19036 KB Output is correct
37 Correct 6 ms 44380 KB Output is correct
38 Correct 20 ms 98344 KB Output is correct
39 Correct 1205 ms 446708 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 11 ms 74496 KB Output is correct
12 Correct 35 ms 140380 KB Output is correct
13 Correct 60 ms 175876 KB Output is correct
14 Correct 6 ms 44376 KB Output is correct
15 Correct 63 ms 193692 KB Output is correct
16 Correct 13 ms 85336 KB Output is correct
17 Correct 4 ms 27480 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 17 ms 98396 KB Output is correct
20 Correct 2 ms 19036 KB Output is correct
21 Correct 1281 ms 426052 KB Output is correct
22 Correct 890 ms 451692 KB Output is correct
23 Correct 865 ms 450984 KB Output is correct
24 Correct 845 ms 451000 KB Output is correct
25 Correct 842 ms 448408 KB Output is correct
26 Correct 850 ms 448572 KB Output is correct
27 Correct 1004 ms 444824 KB Output is correct
28 Correct 1041 ms 447208 KB Output is correct
29 Correct 902 ms 447356 KB Output is correct
30 Correct 943 ms 449144 KB Output is correct
31 Correct 895 ms 448132 KB Output is correct
32 Correct 897 ms 447020 KB Output is correct
33 Correct 840 ms 446060 KB Output is correct
34 Correct 1 ms 2392 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 3 ms 19036 KB Output is correct
37 Correct 6 ms 44380 KB Output is correct
38 Correct 20 ms 98344 KB Output is correct
39 Correct 1205 ms 446708 KB Output is correct
40 Incorrect 0 ms 344 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 11 ms 74496 KB Output is correct
12 Correct 35 ms 140380 KB Output is correct
13 Correct 60 ms 175876 KB Output is correct
14 Correct 6 ms 44376 KB Output is correct
15 Correct 63 ms 193692 KB Output is correct
16 Correct 13 ms 85336 KB Output is correct
17 Correct 4 ms 27480 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 17 ms 98396 KB Output is correct
20 Correct 2 ms 19036 KB Output is correct
21 Correct 1281 ms 426052 KB Output is correct
22 Correct 890 ms 451692 KB Output is correct
23 Correct 865 ms 450984 KB Output is correct
24 Correct 845 ms 451000 KB Output is correct
25 Correct 842 ms 448408 KB Output is correct
26 Correct 850 ms 448572 KB Output is correct
27 Correct 1004 ms 444824 KB Output is correct
28 Correct 1041 ms 447208 KB Output is correct
29 Correct 902 ms 447356 KB Output is correct
30 Correct 943 ms 449144 KB Output is correct
31 Correct 895 ms 448132 KB Output is correct
32 Correct 897 ms 447020 KB Output is correct
33 Correct 840 ms 446060 KB Output is correct
34 Correct 1 ms 2392 KB Output is correct
35 Correct 1 ms 6492 KB Output is correct
36 Correct 3 ms 19036 KB Output is correct
37 Correct 6 ms 44380 KB Output is correct
38 Correct 20 ms 98344 KB Output is correct
39 Correct 1205 ms 446708 KB Output is correct
40 Incorrect 0 ms 344 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 2 ms 10584 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 37 ms 140192 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct
13 Runtime error 22 ms 348 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -