제출 #719732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719732		lam	Copy and Paste 3 (JOI22_copypaste3)	C++14	62 / 100	2979 ms	168268 KiB

copypaste3

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int base = 101LL;
const int mod = 1e9 + 7;
int n,a,b,c;
string s;
const int maxn = 2510;
int pre[maxn][maxn],nnext[maxn][maxn],dp[maxn][maxn];
struct fen_tree2
{
    int f[maxn][maxn];
    void reset(int rt, int sz)
    {
        fill_n(f[rt],sz+1,1e18);
    }
    void update(int rt, int x, int val)
    {
        while (x>0)
        {
            f[rt][x]=min(f[rt][x],val);
            x-=(x&-x);
        }
    }
    int get(int rt, int sz, int x)
    {
        int temp=1e18;
        while (x<=sz)
        {
            temp=min(temp,f[rt][x]);
            x+=(x&-x);
        }
        return temp;
    }
};
fen_tree2 dp2;

map<int,int> mp;

struct fen_tree3
{
    int f[maxn][maxn];
    void reset(int rt, int sz)
    {
        fill_n(f[rt],sz+1,1e18);
    }
    void update(int rt, int sz, int x, int val)
    {
        while (x<=sz)
        {
            f[rt][x]=min(f[rt][x],val);
            x+=(x&-x);
        }
    }
    int get(int rt, int x)
    {
        int temp=1e18;
        while (x>0)
        {
            temp=min(temp,f[rt][x]);
            x-=(x&-x);
        }
        return temp;
    }
};
fen_tree3 dp3;

int h[maxn],p[maxn];
inline int get(int l, int r)
{
    return (h[r]-(h[l-1]*p[r-l+1]%mod)+mod)%mod;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n;
    cin>>s;
    cin>>a>>b>>c;
    p[0]=1LL;
    for (int i=1; i<=n; i++) p[i]=p[i-1]*base%mod;
    h[0]=0LL;
    for (int i=1; i<=n; i++) h[i]=(h[i-1]*base%mod + (s[i-1]-'a'+1))%mod;
    for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++) dp[i][j] = a*(j-i+1);
    for (int i=1; i<=n; i++)
    {
        dp2.reset(i,i);
        dp3.reset(i,n-i+1);
    }
    for (int len=1; len<n; len++)
    {
        mp.clear();
        for (int i=1; i+len-1<=n; i++)
        {
            if (i>len) mp[get(i-len,i-1)] = i-len;
            int j=i+len-1;
            if (!mp.count(get(i,j))) pre[i][j]=-1;
            else pre[i][j]=mp[get(i,j)];
        }
        mp.clear();
        for (int j=n; j>=len; j--)
        {
            int i=j-len+1;
            if (n-j>=len) mp[get(j+1,j+len)] = j+len;
            if (!mp.count(get(i,j))) nnext[i][j]=-1;
            else nnext[i][j]=mp[get(i,j)];
        }
    }
    for (int len=1; len<n; len++)
        for (int j=len; j<=n; j++)
    {
        int i=j-len+1;
        int val = min(dp[i][j],min(dp2.get(j,j,i)-i*a,dp3.get(i,j-i+1)+j*a));
//        cerr<<i<<' '<<j<<" := "<<val<<endl;
        int num = 1;
        int last = i-1;
        int x=i; int y=j;
        while (pre[x][y]!=-1)
        {
            int z = pre[x][y];
//            cerr<<last<<' '<<j<<endl;
            dp2.update(j,last,val+b+num*c+(j+1-(num*len))*a);
            last=z;
            num++;
            x=z; y=z+len-1;
        }
        dp2.update(j,last,val+b+num*c+(j+1-(num*len))*a);
        dp2.update(j,i-1,val+i*a);
//        cerr<<":>"<<endl;
//        for (int z=i-1; z>=1; z--)
//        {
//            if (r-z+1>=len)
//            {
//                if (get(z,z+len-1) == get(i,j))
//                {
//                    num++;
//                    r=z-1;
//                }
//            }
//            dp[z][j]=min(dp[z][j],dp[i][j]+b+num*c+(j-z+1-(num*len))*a);
//            dp[z][j]=min(dp[z][j],dp[i][j]+(i-z)*a);
//        }
        num=1;
        last=j+1;
        x=i; y=j;
        while (nnext[x][y]!=-1)
        {
            int z=nnext[x][y];
            dp3.update(i,n-i+1,last-i+1,val+b+num*c+(-i+1-(num*len))*a);
            last=z;
            num++;
            x=z-len+1; y=z;
        }
//        cerr<<i<<' '<<last<<' '<<num<<endl;
        dp3.update(i,n-i+1,last-i+1,val+b+num*c+(-i+1-(num*len))*a);
        dp3.update(i,n-i+1,2,val+(-j)*a);
//        cerr<<":>"<<endl;
//        int l=j+1;
//        for (int z=j+1; z<=n; z++)
//        {
//            if (z-l+1>=len)
//            {
//                if (get(z-len+1,z) == get(i,j))
//                {
//                    num++;
//                    l=z+1;
//                }
//            }
//            dp[i][z]=min(dp[i][z],dp[i][j]+b+num*c+(z-i+1-(num*len))*a);
//            dp[i][z]=min(dp[i][z],dp[i][j]+(z-j)*a);
//        }
//        cout<<i<<' '<<j<<" := "<<dp[i][j]<<'\n';
    }
    int ans = min(dp[1][n],min(dp2.get(n,n,1)-1*a,dp3.get(1,n)+n*a));
    cout<<ans<<'\n';

}

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