Submission #544571

#	Time	Username	Problem	Language	Result	Execution time	Memory
544571		Rafi22	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	2229 ms	684156 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=2507;

ll DP[N][N];
int id[N][N];
int it;
set<int>V[N*N];
bool was[N*N];
int n;
string s;

void rek(vector<int>v,int l)
{
    vector<int>nx[26];
    if(l>0)
    {
        it++;
        V[it].insert(inf);
        for(auto x:v)
        {
            id[x][x+l-1]=it;
            V[it].insert(x);
        }
    }
    for(auto x:v)
    {
        if(x+l>n) continue;
        nx[s[x+l]-'a'].pb(x);
    }
    for(int i=0;i<26;i++) if(sz(nx[i])>0) rek(nx[i],l+1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll A,B,C;
    cin>>n>>s>>A>>B>>C;
    s='#'+s;
    for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) DP[i][j]=infl;
    for(int i=1;i<=n;i++) DP[i][i]=A;
    vector<int>v(n);
    for(int i=0;i<n;i++) v[i]=i+1;
    rek(v,0);
    for(int d=1;d<=n;d++)
    {
        for(int l=1;l+d-1<=n;l++)
        {
            int r=l+d-1;
            DP[l][r]=min({DP[l][r],DP[l+1][r]+A,DP[l][r-1]+A});
            int x=id[l][r];
            if(was[x]) continue;
            was[x]=1;
            while(sz(V[x])>1)
            {
                vector<int>P;
                int c=-inf;
                while(true)
                {
                    set<int>::iterator I=V[x].upper_bound(c);
                    if(*I==inf) break;
                    P.pb(*I);
                    c=*I+d-1;
                    V[x].erase(I);
                }
                for(int i=0;i<sz(P);i++)
                {
                    for(int j=i;j<sz(P);j++)
                    {
                        ll cost=B+(ll)(j-i+1)*C+(ll)(P[j]+d-P[i]-(j-i+1)*d)*A;
                        DP[P[i]][P[j]+d-1]=min(DP[P[i]][P[j]+d-1],DP[l][r]+cost);
                    }
                }
            }
        }
    }
    cout<<DP[1][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