제출 #583196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583196		balbit	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1547 ms	133008 KiB

copypaste3

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

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i = n-1; i>=0; --i)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2500+5;

int comlen[maxn][maxn];
string s;
int A,B,C; // single letter, cut, paste

int dp[maxn][maxn];
vector<int> todo[maxn];
int nxt[maxn][maxn]; // starting at i, with length j

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    int n; cin>>n;
    cin>>s;
    cin>>A>>B>>C;

    // build comlen
    for (int j = n-1; j>=0; --j) {
        for (int i = j; i>=0; --i) {
            if (s[i] != s[j]) {comlen[i][j] = comlen[j][i] = 0;}
            else{
                comlen[i][j] = comlen[j][i] = 1 + comlen[i+1][j+1];
            }
        }
    }

    REP(i,n) REP(j,i) bug(i,j,comlen[i][j]);
    memset(nxt, -1, sizeof nxt);

    REP(i,n) {
        set<int> have;
        vector<pii> yom;
        for (int j = i+1; j<n; ++j) {
            yom.pb({comlen[i][j], j});
        }
        sort(ALL(yom), greater<pii>());
        int at = 0;
        for (int len = n; len>=1; --len) {
            if (i + len*2 <=n) {
                while (at < SZ(yom) && yom[at].f >= len) {
                    have.insert(yom[at].s); ++at;
                }
                auto it = have.lower_bound(i+len);
                nxt[i][len] = it==have.end()?-1 : *it;
                bug(nxt[i][len]);
            }
        }
    }

    RREP(i,n) {
        REP(j,n) todo[j].clear();
        for (int len = 1; len*2+i<=n; ++len) {
            int at = nxt[i][len];
            while(at != -1) {
                todo[at + len-1].pb(len);
                at = nxt[at][len];
            }
        }
        vector<int> howgood(n+1);
        int best = 0;
        for (int j = i; j<n; ++j) {
            int len = j-i+1;
            dp[i][j] = A + dp[i+1][j];
            for (int t : todo[j]) {
                howgood[t] += -t * A + C;
                MN(best, howgood[t]);
            }

            bug(best);
            MN(dp[i][j], len * A + best);
            howgood[len] = dp[i][j] + B - (len) * A + C;
            MN(best, howgood[len]);

        }
    }

    cout<<dp[0][n-1]<<endl;
}

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