oj.uz

Submission #1004374

# Submission time Handle Problem Language Result Execution time Memory
1004374 2024-06-21T08:22:22 Z De3b0o Copy and Paste 3 (JOI22_copypaste3) C++14
1 / 100
 13 ms 24352 KB 
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)

using namespace std;

ll n;
string s;
ll A , B , C;
bitset<1600000090> e;
ll dp[209][209];
vector<ll> idx[1009][1009];

ll fp(ll x , ll y , ll mod)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2,mod);
    if(y&1)
        return z*z%mod*x%mod;
    else
        return z*z%mod;
}

ll gt(ll i , ll j , ll l1 , ll r1)
{
    ll l = 0 , r = idx[i][j].size()-1;
    ll sum = 0;
    while(l<=r)
    {
        if(idx[i][j][mid]>r1)
            r=mid-1;
        else
        {
            sum=mid+1;
            l=mid+1;
        }
    }
    sum*=(j-i+1);
    return sum;
}

ll solve(ll l , ll r)
{
    if(dp[l][r])
        return dp[l][r];
    ll ans = (r-l+1)*A;
    for(ll i = l ; r>i ; i++)
    {
        for(ll j = i ; r>j ; j++)
        {
            ll ans1 = solve(i,j) + B + (i-l)*A + C;
            ll y = gt(i,j,j+1,r);
            ans1+=y/(j-i+1)*C;
            ans1+=(r-j-y)*A;
            ans=min(ans,ans1);
        }
    }
    dp[l][r]=ans;
    return ans;
}

int main()
{
    mt19937 rnd(time(0));
    cin >> n;
    cin >> s;
    cin >> A >> B >> C;
    ll p1 = 31 , p2 = 29;
    ll mod1 = 1e9+7 , mod2 = 1e9+9;
    for(int l = 1 ; n>=l ; l++)
    {
        map<pll,pll> mp;
        ll hsh1 = 0;
        ll hsh2 = 0;
        ll pr1 = 1;
        ll pr2 = 1;
        for(int i = n-l ; i>n-2*l ; i--)
        {
            ll y = int(s[i]);
            hsh1+=y*pr1;
            hsh1%=mod1;
            pr1*=p1;
            pr1%=mod1;
            hsh2+=y*pr2;
            hsh2%=mod2;
            pr2*=p2;
            pr2%=mod2;
        }
        mp[{hsh1,hsh2}]={n-2*l+1,n-l};
        pr1=fp(p1,l-1,mod1);
        pr2=fp(p2,l-1,mod2);
        for(int j = n-l-1 ; j>=0 ; j--)
        {
            int i = j-l+1;
            ll y = int(s[j+1]);
            hsh1-=y;
            hsh1%=mod1;
            hsh1+=mod1;
            hsh1%=mod1;
            hsh1*=fp(p1,mod1-2,mod1)%mod1;
            y=int(s[i]);
            hsh1+=y*pr1;
            hsh1%=mod1;
            y = int(s[j+1]);
            hsh2-=y;
            hsh2%=mod2;
            hsh2+=mod2;
            hsh2%=mod2;
            hsh2*=fp(p2,mod2-2,mod2)%mod2;
            y=int(s[i]);
            hsh2+=y*pr2;
            hsh2%=mod2;
            if(mp[{hsh1,hsh2}].F!=0)
            {
                idx[i][j]=idx[mp[{hsh1,hsh2}].F][mp[{hsh1,hsh2}].S];
                if(mp[{hsh1,hsh2}].F>j)
                    idx[i][j].pb(mp[{hsh1,hsh2}].S);
            }
            mp[{hsh1,hsh2}]={i,j};
        }
    }
    for(int i = 0 ; n>i ; i++)
        for(int j = i ; n>j ; j++)
            reverse(idx[i][j].begin(),idx[i][j].end());
    ll ans = solve(0,n-1);
    cans
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 10 ms 24156 KB Output is correct
4 Correct 10 ms 24156 KB Output is correct
5 Correct 10 ms 24128 KB Output is correct
6 Correct 10 ms 24156 KB Output is correct
7 Correct 10 ms 24336 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 10 ms 24352 KB Output is correct
10 Correct 10 ms 24156 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 24156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 10 ms 24156 KB Output is correct
4 Correct 10 ms 24156 KB Output is correct
5 Correct 10 ms 24128 KB Output is correct
6 Correct 10 ms 24156 KB Output is correct
7 Correct 10 ms 24336 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 10 ms 24352 KB Output is correct
10 Correct 10 ms 24156 KB Output is correct
11 Correct 10 ms 24152 KB Output is correct
12 Incorrect 11 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 10 ms 24156 KB Output is correct
4 Correct 10 ms 24156 KB Output is correct
5 Correct 10 ms 24128 KB Output is correct
6 Correct 10 ms 24156 KB Output is correct
7 Correct 10 ms 24336 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 10 ms 24352 KB Output is correct
10 Correct 10 ms 24156 KB Output is correct
11 Correct 10 ms 24152 KB Output is correct
12 Incorrect 11 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 10 ms 24156 KB Output is correct
4 Correct 10 ms 24156 KB Output is correct
5 Correct 10 ms 24128 KB Output is correct
6 Correct 10 ms 24156 KB Output is correct
7 Correct 10 ms 24336 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 10 ms 24352 KB Output is correct
10 Correct 10 ms 24156 KB Output is correct
11 Correct 10 ms 24152 KB Output is correct
12 Incorrect 11 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 10 ms 24156 KB Output is correct
3 Correct 10 ms 24156 KB Output is correct
4 Correct 10 ms 24156 KB Output is correct
5 Correct 10 ms 24128 KB Output is correct
6 Correct 10 ms 24156 KB Output is correct
7 Correct 10 ms 24336 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 10 ms 24352 KB Output is correct
10 Correct 10 ms 24156 KB Output is correct
11 Incorrect 10 ms 24156 KB Output isn't correct
12 Halted 0 ms 0 KB -