oj.uz

답안 #895996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895996 2023-12-31T11:46:54 Z alexander707070 Copy and Paste 3 (JOI22_copypaste3) C++14
0 / 100
 52 ms 140368 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){
        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
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 140368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -