Submission #550554

#	Time	Username	Problem	Language	Result	Execution time	Memory
550554		fcmalkcin	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	709 ms	629576 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=2e3+530;
const ll base=3e18;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/// have medal in APIO
/// goal 2/8

ll n, a, b, c;
string s;
ll dp[maxn][maxn];
vector<int> gr[maxn*maxn];
ll cnt=0;
int nxt[maxn*maxn][27];
vector<int> adj[maxn];
void add(string s,ll l)
{
    ll nw=0;
    ll dep=0;
    for (auto to:s)
    {
        dep++;
        ll h=(to-'a'+1);
        if (!nxt[nw][h])
        {
            cnt++;
            nxt[nw][h]=cnt;
            adj[dep].pb(nxt[nw][h]);
        }
        nw=nxt[nw][h];
        gr[nw].pb(l);

    }
}
ll rt[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    cin>> n>> s>> a>> b>> c;
    s=" "+s;
    for (int i=1;i<=n;i++)
    {
        string t=s.substr(i,n-i+1);
        add(t,i);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=i;j<=n;j++)
        {
            dp[i][j]=a*(j-i+1);
        }
    }
    for (int len=1;len<=n;len++)
    {
        for (auto nw:adj[len])
        {
            vector<int> vt=gr[nw];

            ll pre=vt.size();
            for (int i=vt.size()-1;i>=0;i--)
            {
                while (vt[pre-1]-len+1>vt[i]) pre--;
                rt[i]=pre;

            }
            for (int i=0;i<vt.size();i++)
            {
                ll nw=rt[i];
                ll cnt=1;
                while (nw<vt.size())
                {
                    ll l=vt[i];
                    ll r=vt[nw]+len-1;
                    cnt++;
                    dp[l][r]=min(dp[l][r],(r-l+1-cnt*len)*a+b+dp[l][l+len-1]+c*cnt);
               /* if (len==1&&vt[0]==3&&i==0)
            {
                cout <<" chk1"<<endl;
                cout <<l<<" "<<r<<" "<<dp[l][r]<<" "<<dp[l][l+len-1]<<" "<<b*cnt<<" "<<c<<" chk1"<<endl;
            }*/
                    nw=rt[nw];
                }
            }
        }
        for (int i=1;i+len-1<=n;i++)
        {
            ll j=i+len-1;
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a);
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+a);
        }
    }
    cout <<dp[1][n]<<endl;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int i=0;i<vt.size();i++)
      |                          ~^~~~~~~~~~
copypaste3.cpp:90:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 while (nw<vt.size())
      |                        ~~^~~~~~~~~~
copypaste3.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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