oj.uz

Submission #558005

# Submission time Handle Problem Language Result Execution time Memory
558005 2022-05-06T13:16:35 Z DanShaders Copy and Paste 3 (JOI22_copypaste3) C++17
0 / 100
 3000 ms 340 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 2510;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll dp[N][N];
int nxt[N][N];

int pref[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	ll a, b, c;
	string s;
	cin >> n >> s >> a >> b >> c;
	for (int i = 0; i < n; ++i) {
		pref[i] = n - i;
		int zbegin = 0, zend = 0;
		for (int j = i + 1; j < n; ++j) {
			pref[j] = 0;
			if (zend > j) {
				pref[j] = min(zend - j, pref[j - zbegin]);
			}
			while (s[j + pref[j]] == s[i + pref[j]]) {
				++pref[j];
			}
			if (zend < j + pref[j]) {
				zbegin = j;
				zend = j + pref[j];
			}
		}

		for (int j = i + 1; j < n; ++j) {
			nxt[i][j] = n;
			for (int h = 1; h <= min(j - i, pref[j]); ++h) {
				nxt[i][i + h] = min(nxt[i][i + h], j);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			dp[i][j] = (j - i) * a;
		}
	}
	for (int len = 1; len <= n; ++len) {
		for (int i = 0; i <= n - len; ++i) {
			int at = nxt[i][i + len];
			ll curr = dp[i][i + len] + b + 2 * c + (at - i - len) * a;
			while (at != n) {
				dp[i][at + len] = min(curr, dp[i][at + len]);
				int prv = at;
				at = nxt[at][at + len];
				curr += c + (at - prv - len) * a;
			}
		}
		for (int len2 = len; len2 <= n; ++len2) {
			for (int i = 0; i <= n - len2; ++i) {
				dp[i][i + len2] = min({dp[i][i + len2], dp[i][i + len2 - 1] + a, dp[i + 1][i + len2] + a});
			}
		}
	}
	cout << dp[0][n];
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -