Submission #555652

#	Time	Username	Problem	Language	Result	Execution time	Memory
555652		Koosha_mv	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1341 ms	67656 KiB

copypaste3

    #include <bits/stdc++.h>
    using namespace std;
    #pragma GCC optimize "Ofast"
     
    typedef unsigned uint;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef vector<int> vi;
    typedef vector<pii> vpii;
    typedef complex<double> cmplx;
    template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
    #define boost() cin.sync_with_stdio(0); cin.tie(0)
    #define ms(a, x) memset(a, x, sizeof(a))
    #define pb push_back
    #define fs first
    #define sn second
    #define ALL(v) (v).begin(), (v).end()
    #define SZ(v) ((int) (v).size())
    #define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
    #define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
    template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
    const int INF = 0x3f3f3f3f;
    const ll LLINF = 0x3f3f3f3f3f3f3f3f;
    const double PI = acos(-1);
    #define FR(i, n) for(int i = 0; i < (n); i++)
    #define FOR(i, a, b) for(int i = (a); i < (b); i++)
    #define FORR(i, a, b) for(int i = (a); i >= (b); i--)
    #define dbg(x) {cout << #x << ' ' << x << endl;}
    #define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}
     
    const ll MOD = 1e16 + 61;
    const int X = 48394;
    const int MN = 2505;
    int n;
    string str;
    int aCost, bCost, cCost;
    ll hashes[MN][MN];
    ll dp[MN][MN];
    int len;
    vector<pll> vec;
    int arr[MN];
     
    void proc(int l, int r){
        ms(arr, INF);
        ll minCost = 0;
     
        int prv = 0;
        FOR(i, l, r){
            int a = vec[i].sn;
            FOR(j, prv, a+1) arr[j] = a;
            prv = a+1;
            minCost = max(minCost, dp[a][a+len]);
        }
        minCost = (ll) aCost*len - minCost + bCost;
     
        FOR(i, l, r){
            int a = vec[i].sn;
            int pos = a;
            int cur = 0;
            while(arr[pos] != INF){
                pos = arr[pos] + len;
                cur++;
                assert(pos <= n);
                dp[a][pos] = max(dp[a][pos], (ll) cur*len*aCost - minCost - (ll) cur*cCost);
            }
        }
    }
     
    int main(){
        boost();
        cin >> n >> str >> aCost >> bCost >> cCost;
        for(char &ch : str) ch -= 'a';
        FR(i, n) FOR(j, i, n) hashes[i][j+1] = (hashes[i][j]*X + str[j]) % MOD;
     
        for(len = 1; len <= n; len++){
            int num = n-len+1;
            vec.clear();
     
            FR(i, num) vec.pb({hashes[i][i+len], i});
     
            sort(ALL(vec));
            int l = 0;
            FOR(r, 1, num+1){
                if(r == num || vec[r].fs != vec[r-1].fs){
                    proc(l, r);
                    l = r;
                }
            }
     
            FR(i, num){
                if(i) dp[i-1][i+len] = max(dp[i-1][i+len], dp[i][i+len]);
                if(i < num-1) dp[i][i+len+1] = max(dp[i][i+len+1], dp[i][i+len]);
            }
        }
     
        ll ans = (ll) n*aCost - dp[0][n];
        cout << ans << '\n';
    }

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