Submission #580559

#	Time	Username	Problem	Language	Result	Execution time	Memory
580559		CyberSleeper	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	734 ms	82900 KiB

copypaste3

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define pii         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
#define sqr(x)      (x)*(x)
#define arr3        array<ll, 3>
using namespace std;

const ll MX=2502, MOD1=1000000000000027, MOD2=1000000123, BLOCK=160, INF=1e9+7, LG=62, key1=177013, key2=353707;
const ll INFF=1000000000000000004;
const ld ERR=1e-6, pi=3.14159265358979323846;

ll A, B, C, N, hsh[MX][MX], DP[MX][MX];
string S;

int main(){
    fastio;
    cin >> N >> S >> A >> B >> C;
    if(N==1){
        cout << A << nl;
        return 0;
    }
    for(ll i=0; i<=N; i++){
        for(ll j=0; j<=N; j++)
            DP[i][j]=INFF;
    }
    for(ll i=0; i<N; i++){
        for(ll j=i; j<N; j++){
            (hsh[i][j]=hsh[i][j-1]*key1+S[j])%=MOD1;
        }
        DP[i][i]=A;
    }
    for(ll len=0; len<N; len++){
        vector<pll> sub;
        for(ll le=0, ri=le+len; ri<N; le++, ri++){
            DP[le][ri]=min({DP[le][ri], DP[le+1][ri]+A, DP[le][ri-1]+A});
        }
        for(ll i=0; i+len<N; i++){
            sub.pb({hsh[i][i+len], i});
        }
        sort(all(sub));
        vector<ll> nxt(N, -1);
        for(ll i=0; i+len<N; i++){
            ll loc=lower_bound(all(sub), mp(hsh[i][i+len], i+len+1))-sub.begin();
            if(loc<sub.size() && sub[loc].fi==hsh[i][i+len])
                nxt[i]=sub[loc].se;
        }
        for(ll le=0; le+len<N; le++){
            ll idx=nxt[le], cnt=2, ri;
            while(idx!=-1){
                ri=idx+len;
                DP[le][ri]=min(DP[le][ri], DP[le][le+len]+B+C*cnt+A*(ri-le+1-cnt*(len+1)));
                cnt++;
                idx=nxt[idx];
            }
        }
    }
    cout << DP[0][N-1] << nl;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if(loc<sub.size() && sub[loc].fi==hsh[i][i+len])
      |                ~~~^~~~~~~~~~~

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