제출 #1280702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280702		denislav	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	721 ms	59008 KiB

copypaste3

# include <iostream>
# include <vector>
# include <algorithm>
# include <map>
using namespace std;

const long long INF=1e18;
const int MAX=2511;

int n;
long long A,B,C;
char a[MAX];

const long long mod[2]={(long long)1e9+7,(long long)1e9+9};
const long long K=31;

long long power[MAX][2];
void hesh_precalc()
{
    power[0][0]=1;
    power[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        power[i][0]=(power[i-1][0]*K)%mod[0];
        power[i][1]=(power[i-1][1]*K)%mod[1];
    }
}

struct hesh
{
    int len=0;
    long long h[2]={0,0};

    bool friend operator == (hesh _A, hesh _B)
    {
        return _A.len==_B.len and _A.h[0]==_B.h[0] and _A.h[1]==_B.h[1];
    }

    bool friend operator < (hesh _A, hesh _B)
    {
        if(_A.len!=_B.len) return _A.len<_B.len;
        if(_A.h[0]!=_B.h[0]) return _A.h[0]<_B.h[0];
        return _A.h[1]<_B.h[1];
    }

    void add_back(int x)
    {
        h[0]=(h[0]*K+x)%mod[0];
        h[1]=(h[1]*K+x)%mod[1];
        len++;
    }

    void rem_front(int x)
    {
        len--;
        h[0]=(h[0]-power[len][0]*x+mod[0]*x)%mod[0];
        h[1]=(h[1]-power[len][1]*x+mod[1]*x)%mod[1];
    }
};

int c[MAX];
int nxt[MAX][MAX];

long long dp[MAX][MAX];
int cnt[MAX];
vector<int> toAdd[MAX];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>A>>B>>C;

    hesh_precalc();
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++) nxt[i][k]=-1;

        map<hesh,int> mp;
        vector<vector<int>> v(n+1);
        int diff=0;
        hesh H;
        for(int i=1;i<=k;i++) H.add_back(a[i]-'a'+1);

        diff++;
        mp[H]=diff;
        c[1]=diff;
        v[diff].push_back(1);
        for(int i=2;i+k-1<=n;i++)
        {
            H.rem_front(a[i-1]-'a'+1);
            H.add_back(a[i+k-1]-'a'+1);
            if(mp.find(H)==mp.end())
            {
                diff++;
                mp[H]=diff;
                c[i]=diff;
            }
            else c[i]=mp[H];
            v[c[i]].push_back(i);
        }

        for(int d=1;d<=diff;d++)
        {
            int sz=v[d].size(),ptr=0;
            for(int i=0;i<sz;i++)
            {
                while(ptr+1<i and v[d][i]-v[d][ptr+1]>=k) ptr++;
                if(v[d][i]-v[d][ptr]>=k) nxt[v[d][i]][k]=v[d][ptr];
            }
        }

        //cout<<k<<":";
        //for(int i=1;i<=n;i++) cout<<nxt[i][k]<<" ";
        //cout<<"\n";
    }

    for(int r=1;r<=n;r++)
    {
        for(int l=1;l<=r;l++)
        {
            dp[l][r]=INF;
            cnt[l]=0;
            toAdd[l].clear();
        }

        long long mn=0;
        for(int l=r;l>=1;l--)
        {
            for(int k: toAdd[l])
            {
                cnt[k]++;
                mn=min(mn,C*cnt[k]-A*(cnt[k]*k)+B+dp[r-k+1][r]);
                if(nxt[l][k]!=-1) toAdd[nxt[l][k]].push_back(k);
            }

            dp[l][r]=min(dp[l][r],A*(r-l+1)+mn);
            dp[l][r]=min(dp[l][r],dp[l][r-1]+A);

            int k=r-l+1;
            cnt[k]++;
            mn=min(mn,C*cnt[k]-A*(cnt[k]*k)+B+dp[r-k+1][r]);
            if(nxt[l][k]!=-1) toAdd[nxt[l][k]].push_back(k);
        }
    }

    cout<<dp[1][n]<<"\n";

    return 0;
}

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