Submission #904832

#	Time	Username	Problem	Language	Result	Execution time	Memory
904832		Tuanlinh123	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	1473 ms	683348 KiB

copypaste3

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
 
const ll maxn=2505;
vector <ll> pos[maxn*maxn];
ll crr, go[maxn*maxn][26];
long long check[maxn*maxn];
ll pi[maxn][maxn], idx[maxn][maxn], cnt[maxn][maxn], R[maxn][maxn];
 
inline ll calc(ll l, ll r, ll q)
{
    ll id=idx[l][r], len=r-l+1;
    while (1)
    {
        ll p=upper_bound(pos[id].begin(), pos[id].end(), R[l][r])-pos[id].begin();
        if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
        cnt[l][r]++, R[l][r]=pos[id][p]+len-1;
    }
    return cnt[l][r];
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    string s; cin >> s; s='$'+s;
    long long A, B, C; cin >> A >> B >> C;
    for (ll i=1; i<=n; i++)
    {
        for (ll j=i+1; j<=n; j++)
        {
            ll k=pi[i][j-1];
            while (k && s[i+k]!=s[j])
                k=pi[i][i+k-1];   
            pi[i][j]=k+(s[i+k]==s[j]);
        }
        for (ll j=i, p=0; j<=n; j++)
        {
            ll c=s[j]-'a';
            if (!go[p][c]) go[p][c]=++crr;
            p=go[p][c], idx[i][j]=p;
            pos[idx[i][j]].pb(i);
            R[i][j]=j, cnt[i][j]=1;
        }
    }
    for (ll len=1; len<=n; len++)
    {
        for (ll i=1; i+len<=n+1; i++)
        {
            ll j=i+len-1, crr=pi[i][j];
            if (check[idx[i][j]])
                continue;
            check[idx[i][j]]=A*len;
            if (i<j) check[idx[i][j]]=min({check[idx[i][j]], check[idx[i+1][j]]+A, check[idx[i][j-1]]+A});
            for (; crr; crr=pi[i][i+crr-1])
            {
                ll c=calc(i, i+crr-1, j);
                long long val=check[idx[i][i+crr-1]];
                check[idx[i][j]]=min(check[idx[i][j]], val+B+C*c+A*(len-crr*c));
            }
        }
    }
    cout << check[idx[1][n]];
}

Compilation message (stderr)

copypaste3.cpp: In function 'int calc(int, int, int)':
copypaste3.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
      |             ~^~~~~~~~~~~~~~~~

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