Submission #904761

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

copypaste3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#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 p=31, maxn=2505;
const long long Mod=1e9+7;
vector <ll> pos[maxn*maxn];
long long Hash[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 <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++)
        {
            Hash[i][j]=(Hash[i][j-1]*p+s[j]-'a'+1)%Mod;
            num.pb(Hash[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(), Hash[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 (ll k=i; k<j; k++)
            {
                ll crr=k-i+1, 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:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
      |             ~^~~~~~~~~~~~~~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:66:27: warning: unused variable 'crr' [-Wunused-variable]
   66 |             ll j=i+len-1, crr=pi[i][j];
      |                           ^~~

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