Submission #617435

#	Time	Username	Problem	Language	Result	Execution time	Memory
617435		patrikpavic2	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	602 ms	101084 KiB

copypaste3

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

#define PB push_back

using namespace std;

typedef long long ll;
typedef vector < int > vi;

const int N = 2550;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int BASE1 = 1e6 + 3;
const int BASE2 = 31337;

inline int add1(int A, int B){
	if(A + B >= MOD1)
		return A + B - MOD1;
	return A + B;
}

inline int sub1(int A, int B){
	if(A - B < 0)
		return A - B + MOD1;
	return A - B;
}

inline int mul1(int A, int B){
	return (ll)A * B % MOD1;
}

inline int add2(int A, int B){
	if(A + B >= MOD2)
		return A + B - MOD2;
	return A + B;
}

inline int sub2(int A, int B){
	if(A - B < 0)
		return A - B + MOD2;
	return A - B;
}

inline int mul2(int A, int B){
	return (ll)A * B % MOD2;
}

ll dp[N][N], A, B, C;
vi divv[N];
int pot1[N], pot2[N], n;
ll HSH[N][N];
int nxt[N][N], hsh1[N], hsh2[N];
char s[N];
unordered_map < ll, int > bio;

int get_hsh1(int l, int r){
	return mul1(sub1(hsh1[r], (l ? hsh1[l - 1] : 0)), pot1[N - r - 1]);
}

int get_hsh2(int l, int r){
	return mul2(sub2(hsh2[r], (l ? hsh2[l - 1] : 0)), pot2[N - r - 1]);
}

void precompute(){
	pot1[0] = 1; pot2[0] = 1;
	for(int i = 1;i < N;i++)
		pot1[i] = mul1(pot1[i - 1], BASE1);
	for(int i = 1;i < N;i++)
		pot2[i] = mul2(pot2[i - 1], BASE2);
	for(int i = 0;i < n;i++){
		hsh1[i] = add1(mul1(s[i], pot1[i]), (i ? hsh1[i - 1] : 0));
		hsh2[i] = add2(mul2(s[i], pot2[i]), (i ? hsh2[i - 1] : 0));
	}
	for(int i = 0;i < n;i++)
		for(int j = i;j < n;j++)
			HSH[i][j] = get_hsh1(i, j) * MOD2 + get_hsh2(i, j);
	for(int ln = 1;ln <= n;ln++){
		bio.clear();
		for(int i = n - ln;i >= 0;i--){
			if(i + 2 * ln <= n)
				bio[HSH[i + ln][i + 2 * ln - 1]] = i + ln;
			if(bio[HSH[i][i + ln - 1]]){
				nxt[i][ln] = bio[HSH[i][i + ln - 1]];
			}
		}
	}
}


void dinamika(){
	for(int l = n - 1;l >= 0;l--){
		dp[l][l] = A;
		for(int r = l + 1;r <= n;r++)
			dp[l][r] = A + dp[l + 1][r];
		for(int k = 1;2 * k <= n - l;k++){
			if(k - 1) 
				dp[l][l + k - 1] = min(dp[l][l + k - 1], dp[l][l + k - 2] + A);
			ll cur = dp[l][l + k - 1] + B + C;
			int zad = l;
			while(nxt[zad][k]){
				cur += C + A * (nxt[zad][k] - (zad + k));
				zad = nxt[zad][k];
				dp[l][zad + k - 1] = min(dp[l][zad + k - 1], cur);
			}
		}
		for(int i = l + 1;i < n;i++)
			dp[l][i] = min(dp[l][i], dp[l][i - 1] + A);
	}
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d%s%lld%lld%lld", &n, s, &A, &B, &C);
	precompute();
	dinamika();
	printf("%lld\n", dp[0][n - 1]);
	return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d%s%lld%lld%lld", &n, s, &A, &B, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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