Submission #904808

#	Time	Username	Problem	Language	Result	Execution time	Memory
904808		Tuanlinh123	Copy and Paste 3 (JOI22_copypaste3)	C++17	30 / 100	795 ms	553872 KiB

copypaste3

#include<bits/stdc++.h>
#define ii __int128_t
#define ll long long
#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;
const long long p1=47, p2=101, p3=197, Mod1=998244353, Mod2=1e9+21, Mod3=1e9+7;
vector <ll> pos[maxn*maxn];
long long Hash1[maxn][maxn], Hash2[maxn][maxn], Hash3[maxn][maxn], 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;
    vector <pair<pair<long long, long long>, long long>> num;
    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][k-1];   
            pi[i][j]=k+(s[i+k]==s[j]);
        }
        for (ll j=i; j<=n; j++)
        {
            Hash1[i][j]=(Hash1[i][j-1]*p1+s[j])%Mod1;
            Hash2[i][j]=(Hash2[i][j-1]*p2+s[j])%Mod2;
            Hash3[i][j]=(Hash3[i][j-1]*p3+s[j])%Mod3;
            num.pb({{Hash1[i][j], Hash2[i][j]}, Hash3[i][j]}), R[i][j]=j, cnt[i][j]=1;
        }
    }
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end())-num.begin());
    for (ll i=1; i<=n; i++)
        for (ll j=i; j<=n; j++)
        {
            idx[i][j]=lower_bound(num.begin(), num.end(), mp(mp(Hash1[i][j], Hash2[i][j]), Hash3[i][j]))-num.begin();
            pos[idx[i][j]].pb(i);
        }
    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])
                if (crr*2<=len)
                {
                    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 'long long int calc(long long int, long long int, long long int)':
copypaste3.cpp:24:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         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: 0 / 32
• Subtask 6: 0 / 38