Submission #598896

#	Time	Username	Problem	Language	Result	Execution time	Memory
598896		Arnch	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	3059 ms	20572 KiB

copypaste3

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e3 + 10, pr = 1000696969, mod = 1e9 + 9;

ll ha[N][N];
ll dp[N][N];

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

	int n; cin >>n;
	string s; cin >>s;
	ll A, B, C; cin >>A >>B >>C;

	for(int i = 0; i < n; i++) dp[i][i] = A;

	for(int i = 0; i < n; i++) ha[i][0] = (s[i] - 'a');
	for(int len = 1; len < n; len++)
		for(int i = 0; i < n - len; i++)
			ha[i][len] = (ha[i][len - 1] * pr + (s[i + len] - 'a')) % mod;

	for(int len = 1; len < n; len++) {
		for(int i = 0; i < n - len; i++) {
			int j = i + len;
			dp[i][j] = dp[i][j - 1] + A;
			for(int k = j; k > i; k--) {
				int nu = j - k;
				ll cnt = dp[k][j] + B, val = ha[k][nu], sum = cnt + C;
				for(int x = i; x < k;) {
					if(x + nu >= k || ha[x][nu] != val) {
						x++;
						sum += A;
					}
					else {
						x += nu + 1;
						sum += C;
					}
				}
				dp[i][j] = min(dp[i][j], sum);
			}
		}
	}

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


    return 0;
}

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