Submission #549428

#	Time	Username	Problem	Language	Result	Execution time	Memory
549428		keta_tsimakuridze	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	588 ms	49668 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"

const int N = 25e2 + 5, mod = 1e9 + 7;
const ll inf = 1e14; //!
int t, h[N], nxt[N];
vector<int> v[N];
ll dp[N][N];
main() {
	ios_base::sync_with_stdio(false),
	cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	s = '#' + s;
	int A,B,C;
	cin >> A >> B >> C;
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) dp[i][j] = inf;
		for(int j = i; j <= n; j++) dp[i][j] = (ll)(j - i + 1) * A;
	}
	int p = 37;
	for(int len = 1; len <= n; len++) {
		vector<pii> x;
		for(int i = 1; i <= n - len + 1; i++) {
			h[i] = ((ll)h[i] * p + (s[i + len - 1] - 'a' + 1) ) % mod;
			dp[i][i + len - 1] = min(dp[i][i + len - 1], min(dp[i + 1][i + len - 1] + A , dp[i][i + len - 2] + A));
			x.push_back({h[i], i});
		}
		sort(x.begin(), x.end());
		int cur = 0;
		for(int i = 0; i < x.size(); i++) {
			if(!i || x[i].f != x[i - 1].f) cur++;
			v[cur].push_back(x[i].s);
		}
		for(int i = 1; i <= cur; i++) {
			for(int j = (int)v[i].size() - 1; j >= 0; j--) {
					int l = j + 1, r = v[i].size();// cnt++;
					int x = r; r--;
					while(l <= r) {
						int mid = (l + r) / 2;
						if(v[i][mid] >= v[i][j] + len) x = mid, r = mid - 1;
						else l = mid + 1;
					}
					nxt[j] = x;
					
			}
			for(int j = 0; j < v[i].size(); j++) {
				int cur = j, cnt = 0;
				while(cur < v[i].size()) { 					
					int l = v[i][j], r = v[i][cur] + len - 1;
			//		cout << dp[l][r] << endl;
					dp[l][r] = min(dp[l][r], 
					(ll)(cnt + 1) * C + (ll)(r - l + 1 - (cnt + 1) * len) * A + B + dp[l][l + len - 1 ]);
					cnt++;
					int x = nxt[cur];
					
					if(x == v[i].size()) break;

					cur = x;
					
				}
			}

			v[i].clear();
		}
	}
	cout << dp[1][n];

}

Compilation message (stderr)

copypaste3.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main() {
      | ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int i = 0; i < x.size(); i++) {
      |                  ~~^~~~~~~~~~
copypaste3.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for(int j = 0; j < v[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~
copypaste3.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while(cur < v[i].size()) {
      |           ~~~~^~~~~~~~~~~~~
copypaste3.cpp:66:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |      if(x == v[i].size()) break;
      |         ~~^~~~~~~~~~~~~~

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