Submission #1108918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108918		akim9905	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	590 ms	174320 KiB

copypaste3

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

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define endl "\n"
#define sp " "
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define rz resize
#define sz(a) (int)(a.size())
#define clr(a) a.clear()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef pair<double, int> pdi;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 2525; // PLZ CHK!

template <ll P, ll M> struct Hash {
    vector<ll> H,B;
    void build(const string &S) {
        H.resize(sz(S)+1), B.resize(sz(S)+1);
        B[0]=1;
        for (int i=1; i<=sz(S); i++) H[i]=(H[i-1]*P+S[i-1])%M;
        for (int i=1; i<=sz(S); i++) B[i]=B[i-1]*P%M;
    }

    ll get(int s, int e) {
        return (H[e]-H[s-1]*B[e-s+1]%M+M)%M;
    }
};

Hash<1299709, 1'000'000'007> H1;
Hash<1301021, 1'000'000'009> H2;

int N;

ll A,B,C,D[MAX][MAX],I[MAX][MAX];
string S;

int main() {
    fio();

    cin>>N>>S>>A>>B>>C;
    H1.build(S), H2.build(S);
    S=' '+S;

    vector<pair<pll,pii>> idx;
    for (int i=1; i<=N; i++) {
        for (int j=i; j<=N; j++) {
            idx.pb({{H1.get(i,j),H2.get(i,j)}, {i,j}});
        }
    }

    fill_n(&I[0][0],MAX*MAX,N+10);
    sort(all(idx));
    for (int i=0; i<sz(idx);) {
        int j=i;
        queue<int> q;
        while (j<sz(idx) && idx[i].first==idx[j].first) {
            auto [h,p]=idx[j]; auto [s,e]=p;
            while (!q.empty() && idx[q.front()].second.second<s) {
                auto [ht,pt]=idx[q.front()]; auto [st,et]=pt;
                I[st][et]=s;
                q.pop();
            }
            q.push(j);
            j++;
        }
        i=j;
    }

    fill_n(&D[0][0],MAX*MAX,LINF);

    for (int i=1; i<=N; i++) D[i][i]=A+B;
    for (int i=1; i<=N; i++) {
        for (int l=1,r=l+i-1; r<=N; l++,r++) {
            if (l>1) D[l-1][r]=min(D[l-1][r], A+D[l][r]);
            if (r<N) D[l][r+1]=min(D[l][r+1], A+D[l][r]);

            int cur=I[l][r], cnt=2;
            while (cur+i-1<=N) {
                D[l][cur+i-1]=min(D[l][cur+i-1], D[l][r]+C*cnt+A*(cur+i-l-cnt*i)+B);
                cnt++,cur=I[cur][cur+i-1];
            }
        }
    }

    cout<<D[1][N]-B;

    return 0;
}

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