제출 #585772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585772		Drew_	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	778 ms	72884 KiB

copypaste3

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

#define pb push_back
#define ll long long
#define ii pair<int, int>
#define f1 first
#define s2 second

const int prime = 177013;
const int mod1 = 1e9 + 9;
const int mod2 = 420691273;
const int MAX = 2569;
const ll inf = 1e18 + 69;

template<int KEY1 = mod1, int KEY2 = mod2>
struct Hash
{
    template<int MOD>
    struct Mint
    {
        int val;

        Mint() : val(0) {}
        Mint(int64_t _val) : val((int)(_val % MOD)) { if (val < 0) val += MOD; }

        Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
        Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
        Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }

        friend Mint fpow(Mint x, int64_t y)
        {
            Mint res = 1;
            for (; y > 0; y >>= 1, x *= x)
            {
                if (y & 1)
                    res *= x;
            }
            return res;
        }
        friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
        Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }

        friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
        friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
        friend Mint operator- (Mint a) { return 0 - a; }
        friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
        friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
        friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
        friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
        friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
    };

    Mint<KEY1> val1;
    Mint<KEY2> val2;

    Hash() : val1(0), val2(0) {}
    Hash(int64_t _val) : val1(_val), val2(_val) {}

    Hash& operator+= (const Hash &rhs) { val1 += rhs.val1; val2 += rhs.val2; return *this; }
    Hash& operator-= (const Hash &rhs) { val1 -= rhs.val1; val2 -= rhs.val2; return *this; }
    Hash& operator*= (const Hash &rhs) { val1 *= rhs.val1; val2 *= rhs.val2; return *this; }
    Hash& operator/= (const Hash &rhs) { val1 /= rhs.val1; val2 /= rhs.val2; return *this; }

    friend Hash operator+ (Hash a, const Hash &b) { return a += b; }
    friend Hash operator- (Hash a, const Hash &b) { return a -= b; }
    friend Hash operator- (Hash a) { return 0 - a; }
    friend Hash operator* (Hash a, const Hash &b) { return a *= b; }
    friend Hash operator/ (Hash a, const Hash &b) { return a /= b; }
    friend ostream& operator<< (ostream &os, const Hash &a) { return os << a.val1 << " " << a.val2; }
    friend bool operator== (const Hash &a, const Hash &b) { return a.val1 == b.val1 && a.val2 == b.val2; }
    friend bool operator!= (const Hash &a, const Hash &b) { return a.val1 != b.val1 || a.val2 != b.val2; }
};


ll A, B, C;
int N;
char s[MAX];

Hash<> pwr[MAX], inv[MAX], pfx[MAX];

int nxt[MAX][MAX]; // nxt[l][r]: smallest `x` such that x >= r and s.substr(l, r-l) = s.substr(x, r-l)
ll dp[MAX][MAX]; // dp[l][r]: lowest cost to make x == "" and y == s.substr(l, r-l) 

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	pwr[0] = 1;
	for (int i = 1; i < MAX; ++i)
		pwr[i] = prime * pwr[i-1];
	inv[MAX-1] = 1 / (pwr[MAX-1]);
	for (int i = MAX-2; i >= 0; --i)
		inv[i] = prime * inv[i+1];

	for (auto &x : dp)
		for (auto &y : x)
			y = inf;

	cin >> N >> s >> A >> B >> C;

	pfx[0] = s[0];
	for (int i = 1; i < N; ++i)
		pfx[i] = pfx[i-1] + s[i] * pwr[i];

	const auto getSum = [&](int l, int r) -> ii
	{
		Hash<> tmp = (pfx[r] - (l ? pfx[l-1] : 0)) * inv[l];
		return { tmp.val1.val, tmp.val2.val }; 
	};

	for (int len = 1; len <= N; ++len)
	{
		map<ii, vector<int>> memo;
		for (int l = 0; l+len <= N; ++l)
			memo[getSum(l, l+len-1)].pb(l);

		for (const auto &[x, v] : memo)
		{
			// cerr << "HAHA\n";
			for (int i = 0, j = 0, sz = (int)v.size(); i < sz; ++i)
			{
				while (j < sz && v[i]+len > v[j]) ++j;
				nxt[v[i]][v[i] + len] = (j == sz ? N : v[j]);
			}
		}
	}

	for (int i = 0; i < N; ++i)
		dp[i][i+1] = A + B;

	for (int len = 1; len < N; ++len)
	{
		for (int l = 0; l+len <= N; ++l)
		{
			int r = l + len;
			if (l) dp[l-1][r] = min(dp[l-1][r], dp[l][r] + A);
			if (r+1 <= N) dp[l][r+1] = min(dp[l][r+1], dp[l][r] + A);

			for(int cur = l, ctr = 1; nxt[cur][cur + len] < N;)
			{
				cur = nxt[cur][cur + len];
				ctr++;
				dp[l][cur + len] = min(dp[l][cur + len], dp[l][r] + C*ctr + A*(cur+len - l - ctr*len) + B);
			}
		}
	}


	cout << dp[0][N] - B << '\n';
	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