답안 #544675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544675	2022-04-02T14:20:53 Z	blue	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	592 ms	98764 KB

copypaste3

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())

const ll INF = 1'000'000'000'000'000'000LL;


const int mx = 2'500;

const ll mod = 1'000'000'000'000'007LL;


ll mul(ll a, ll b)
{
	return (a*b)%mod;
}

const int pr = 59;
ll P[1+mx];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	string S;
	cin >> S;
	S = " " + S;

	ll A, B, C;
	cin >> A >> B >> C;

	ll DP[1+N][1+N];
	for(int l = 1; l <= N; l++)
		for(int r = l; r <= N; r++)
			DP[l][r] = A * (r-l+1);

	P[0] = 1;
	P[1] = pr;
	for(int i = 2; i <= N; i++)
		P[i] = mul(P[i-1], pr);


	ll hsh[1+N][1+N];
	for(int l = 1; l <= N; l++)
	{
		hsh[l][l] = (S[l] - 'a' + 1);
		for(int r = l+1; r <= N; r++)
		{
			hsh[l][r] = (hsh[l][r-1] * P[1]  +  (S[r] - 'a' + 1)) % mod;
		}
	}

	// cerr << "done\n";


	for(int d = 0; d < N; d++)
	{
		// cerr << "\n\n\n\n";
		// cerr << "d = " << d << '\n';
		vi nxt(1+N, 0);
		for(int r = d; r <= N; r++)
			nxt[r] = r;

		vector<pll> values;
		for(int l = 1; l+d <= N; l++)
			values.push_back({hsh[l][l+d], l+d});

		// for(pll v : values) cerr << v.first << "/" << v.second << " ";
		// 	cerr << '\n';

		sort(values.begin(), values.end());

		// cerr << "?\n";

		while(!values.empty())
		{
			ll ch = values.back().first;

			// cerr << "ch = " << ch << '\n';
			// cerr << sz(values) << '\n';

			for(int li = sz(values)-1; li >= 0 && values[li].first == ch; li--)
			{
				// cerr << "li = " << li << '\n';
				while(sz(values)-1 > li && values[sz(values)-2].second >= values[li].second + d + 1)
					values.pop_back();

				if(values.back().second >= values[li].second + d + 1)
					nxt[ values[li].second ] = values.back().second;
				// cerr << "dn\n";
			}

			while(!values.empty() && values.back().first == ch)
				values.pop_back();
		}
		// cerr << "#\n";

		// cerr << "nxt = ";
		// for(int l = 1; l <= N; l++) cerr << nxt[l] << ' ';
		// 	cerr << '\n';

		if(d > 0)
		{
			for(int l = 1; l+d <= N; l++)
			{
				int r = l+d;
				DP[l][r] = min(DP[l][r], min(A + DP[l+1][r], DP[l][r-1] + A));
			}
		}


		for(int r = 1+d; r <= N; r++)
		{
			int l = r-d;
			int nr = r;
			for(int ct = 2; 1; ct++)
			{
				if(nxt[nr] == nr) break;
				nr = nxt[nr];

				// cerr << l << ' ' << r << " -> " << ct << " ? " << nr << '\n';

				// cerr << nr-l+1 - ct*(d+1) << " AAA \n";

				DP[l][nr] = min(DP[l][nr], DP[l][r] + B + C*ct + A*(nr-l+1 - ct*(d+1)));
			}

			// cerr << l << ' ' << r << " : " << DP[l][r] << '\n';
		}
	}

	cout << DP[1][N] << '\n';
}

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	212 KB	Output is correct
3	Correct	234 ms	52756 KB	Output is correct
4	Correct	287 ms	61524 KB	Output is correct
5	Correct	334 ms	72124 KB	Output is correct
6	Correct	407 ms	84116 KB	Output is correct
7	Correct	465 ms	98360 KB	Output is correct
8	Correct	474 ms	98352 KB	Output is correct
9	Correct	559 ms	98764 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	2 ms	852 KB	Output is correct
42	Correct	3 ms	852 KB	Output is correct
43	Correct	3 ms	852 KB	Output is correct
44	Correct	3 ms	852 KB	Output is correct
45	Correct	3 ms	852 KB	Output is correct
46	Correct	2 ms	852 KB	Output is correct
47	Correct	3 ms	852 KB	Output is correct
48	Correct	3 ms	848 KB	Output is correct
49	Correct	3 ms	896 KB	Output is correct
50	Correct	3 ms	852 KB	Output is correct
51	Correct	4 ms	852 KB	Output is correct
52	Correct	3 ms	852 KB	Output is correct
53	Correct	3 ms	852 KB	Output is correct

Subtask #5
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	0 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	1 ms	340 KB	Output is correct
41	Correct	2 ms	852 KB	Output is correct
42	Correct	3 ms	852 KB	Output is correct
43	Correct	3 ms	852 KB	Output is correct
44	Correct	3 ms	852 KB	Output is correct
45	Correct	3 ms	852 KB	Output is correct
46	Correct	2 ms	852 KB	Output is correct
47	Correct	3 ms	852 KB	Output is correct
48	Correct	3 ms	848 KB	Output is correct
49	Correct	3 ms	896 KB	Output is correct
50	Correct	3 ms	852 KB	Output is correct
51	Correct	4 ms	852 KB	Output is correct
52	Correct	3 ms	852 KB	Output is correct
53	Correct	3 ms	852 KB	Output is correct
54	Correct	13 ms	3480 KB	Output is correct
55	Correct	58 ms	16032 KB	Output is correct
56	Correct	64 ms	15956 KB	Output is correct
57	Correct	54 ms	16032 KB	Output is correct
58	Correct	55 ms	16036 KB	Output is correct
59	Correct	52 ms	16032 KB	Output is correct
60	Correct	60 ms	16032 KB	Output is correct
61	Correct	64 ms	16028 KB	Output is correct
62	Correct	63 ms	16036 KB	Output is correct
63	Correct	68 ms	16024 KB	Output is correct
64	Correct	62 ms	16052 KB	Output is correct
65	Correct	78 ms	16028 KB	Output is correct
66	Correct	76 ms	16024 KB	Output is correct
67	Correct	52 ms	16036 KB	Output is correct

Subtask #6
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	234 ms	52756 KB	Output is correct
14	Correct	287 ms	61524 KB	Output is correct
15	Correct	334 ms	72124 KB	Output is correct
16	Correct	407 ms	84116 KB	Output is correct
17	Correct	465 ms	98360 KB	Output is correct
18	Correct	474 ms	98352 KB	Output is correct
19	Correct	559 ms	98764 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Correct	1 ms	212 KB	Output is correct
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	212 KB	Output is correct
43	Correct	0 ms	212 KB	Output is correct
44	Correct	1 ms	212 KB	Output is correct
45	Correct	1 ms	212 KB	Output is correct
46	Correct	1 ms	212 KB	Output is correct
47	Correct	1 ms	212 KB	Output is correct
48	Correct	1 ms	212 KB	Output is correct
49	Correct	1 ms	212 KB	Output is correct
50	Correct	1 ms	212 KB	Output is correct
51	Correct	0 ms	212 KB	Output is correct
52	Correct	0 ms	212 KB	Output is correct
53	Correct	1 ms	212 KB	Output is correct
54	Correct	1 ms	212 KB	Output is correct
55	Correct	1 ms	212 KB	Output is correct
56	Correct	1 ms	212 KB	Output is correct
57	Correct	1 ms	340 KB	Output is correct
58	Correct	2 ms	852 KB	Output is correct
59	Correct	3 ms	852 KB	Output is correct
60	Correct	3 ms	852 KB	Output is correct
61	Correct	3 ms	852 KB	Output is correct
62	Correct	3 ms	852 KB	Output is correct
63	Correct	2 ms	852 KB	Output is correct
64	Correct	3 ms	852 KB	Output is correct
65	Correct	3 ms	848 KB	Output is correct
66	Correct	3 ms	896 KB	Output is correct
67	Correct	3 ms	852 KB	Output is correct
68	Correct	4 ms	852 KB	Output is correct
69	Correct	3 ms	852 KB	Output is correct
70	Correct	3 ms	852 KB	Output is correct
71	Correct	13 ms	3480 KB	Output is correct
72	Correct	58 ms	16032 KB	Output is correct
73	Correct	64 ms	15956 KB	Output is correct
74	Correct	54 ms	16032 KB	Output is correct
75	Correct	55 ms	16036 KB	Output is correct
76	Correct	52 ms	16032 KB	Output is correct
77	Correct	60 ms	16032 KB	Output is correct
78	Correct	64 ms	16028 KB	Output is correct
79	Correct	63 ms	16036 KB	Output is correct
80	Correct	68 ms	16024 KB	Output is correct
81	Correct	62 ms	16052 KB	Output is correct
82	Correct	78 ms	16028 KB	Output is correct
83	Correct	76 ms	16024 KB	Output is correct
84	Correct	52 ms	16036 KB	Output is correct
85	Correct	138 ms	39500 KB	Output is correct
86	Correct	375 ms	98360 KB	Output is correct
87	Correct	378 ms	98364 KB	Output is correct
88	Correct	395 ms	98360 KB	Output is correct
89	Correct	358 ms	98408 KB	Output is correct
90	Correct	333 ms	98364 KB	Output is correct
91	Correct	525 ms	98404 KB	Output is correct
92	Correct	532 ms	98368 KB	Output is correct
93	Correct	382 ms	98356 KB	Output is correct
94	Correct	381 ms	98356 KB	Output is correct
95	Correct	516 ms	98432 KB	Output is correct
96	Correct	592 ms	98532 KB	Output is correct
97	Correct	368 ms	98364 KB	Output is correct

답안 #544675

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 5.0 / 5.0

Subtask #3 14.0 / 14.0

Subtask #4 10.0 / 10.0

Subtask #5 32.0 / 32.0

Subtask #6 38.0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
5.0 / 5.0

Subtask #3
14.0 / 14.0

Subtask #4
10.0 / 10.0

Subtask #5
32.0 / 32.0

Subtask #6
38.0 / 38.0