제출 #587568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587568		LastRonin	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	1584 ms	20088 KiB

copypaste3

#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 211 + 1;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

ll n;
string a;
ll dp[N][N], dp2[N];
ll A, B, C;

bool eq[N][N][N];

int main() {
	speed;
	cin >> n;
	cin >> a;
	cin >> A >> B >> C;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dp[i][j] = 1e15;
			for(int st = 1; st <= n; st++) {
				if(a[i + st - 1] != a[j + st - 1])
					break;
				eq[i][j][st] = 1;
			}
		}
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 0; i + k - 1 < n; i++) {
			dp[i][i + k - 1] = min(dp[i][i + k - 1], A * k + B);
			for(int j = 0; j < n; j++) {
				for(int z = j; z <= n; z++) {
					dp2[z] = 1e15;	
				}
				dp2[j] = dp[i][i + k - 1];
				for(int z = j; z < n; z++) {
					if(eq[i][z][k])
						dp2[z + k] = min(dp2[z + k], dp2[z] + C);
					dp2[z + 1] = min(dp2[z + 1], dp2[z] + A);
				}
				for(int z = j + 1; z <= n; z++) {
					dp[j][z - 1] = min(dp[j][z - 1], dp2[z] + B); 
				}
		 	}
    	}
    }
    cout << dp[0][n - 1] - B;
}

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