Submission #553070

#	Time	Username	Problem	Language	Result	Execution time	Memory
553070		BalintR	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	1367 ms	34148 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 int MOD = 2e9 + 11;
const int X = 48394;
const int MN = 2505;
int n;
string str;
int aCost, bCost, cCost;
ll pws[MN], hashes[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';
    pws[0] = 1;
    FR(i, n) pws[i+1] = pws[i] * X % MOD;
    FR(i, n) hashes[i+1] = (hashes[i]*X + str[i]) % MOD;

    for(len = 1; len <= n; len++){
        int num = n-len+1;
        vec.clear();

        FR(i, num){
            ll hash = (hashes[i+len] - hashes[i]*pws[len]) % MOD;
            if(hash < 0) hash += MOD;
            vec.pb({hash, 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: 0 / 38