Submission #544544

#	Time	Username	Problem	Language	Result	Execution time	Memory
544544		benson1029	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	2982 ms	348616 KiB

copypaste3

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

int n;
string s;
long long a,b,c;
long long dp[2505][2505];
int nxt[2505][2505];
unordered_map< long long, vector<int> > hashes[2505];
long long mod = 888888877777777LL;
long long inf = 1e18;

int main() {
	cin >> n;
	cin >> s;
	cin >> a >> b >> c; 
	for(int i=0; i<s.length(); i++) hashes[i].reserve(n); 
	for(int i=0; i<s.length(); i++) {
		long long tmp = 0;
		for(int j=i; j<s.length(); j++) {
			tmp = (tmp * 27 + s[j] - 'a' + 1) % mod;
			hashes[j-i][tmp].push_back(i);
			nxt[i][j] = -1;
			dp[i][j] = inf;
		}
	}
	for(int i=0; i<s.length(); i++) {
		long long tmp = 0;
		for(int j=i; j<s.length(); j++) {
			tmp = (tmp * 27 + s[j] - 'a' + 1) % mod;
			if(hashes[j-i][tmp].size() > 0) {
				int ptr = 0;
				for(int k=0; k<hashes[j-i][tmp].size(); k++) {
					while(ptr < hashes[j-i][tmp].size() && hashes[j-i][tmp][ptr] - hashes[j-i][tmp][k] < j-i+1) ptr++;
					if(ptr < hashes[j-i][tmp].size()) {
						nxt[hashes[j-i][tmp][k]][hashes[j-i][tmp][k]+j-i] = hashes[j-i][tmp][ptr];
					}
				}
				hashes[j-i][tmp].clear();
			}
		}
	}
	
	for(int sz=0; sz<s.length(); sz++) {
		for(int i=0; i<s.length()-sz; i++) {
			int j = i + sz;
			if(sz!=0) {
				dp[i][j] = min(dp[i][j], dp[i+1][j] + a);
				dp[i][j] = min(dp[i][j], dp[i][j-1] + a);
			} else dp[i][j] = a;
			int ptr = i;
			int cnt = 1;
			while(nxt[ptr][ptr+sz] != -1) {
				ptr = nxt[ptr][ptr+sz];
				cnt++;
				dp[i][ptr+sz] = min(dp[i][ptr+sz], dp[i][j] + b + c*cnt + a*(ptr+sz-i+1-cnt*(j-i+1)));
			}
		}
	}
	
	cout << dp[0][s.length()-1] << "\n";
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i<s.length(); i++) hashes[i].reserve(n);
      |               ~^~~~~~~~~~~
copypaste3.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0; i<s.length(); i++) {
      |               ~^~~~~~~~~~~
copypaste3.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int j=i; j<s.length(); j++) {
      |                ~^~~~~~~~~~~
copypaste3.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0; i<s.length(); i++) {
      |               ~^~~~~~~~~~~
copypaste3.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int j=i; j<s.length(); j++) {
      |                ~^~~~~~~~~~~
copypaste3.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int k=0; k<hashes[j-i][tmp].size(); k++) {
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |      while(ptr < hashes[j-i][tmp].size() && hashes[j-i][tmp][ptr] - hashes[j-i][tmp][k] < j-i+1) ptr++;
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |      if(ptr < hashes[j-i][tmp].size()) {
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int sz=0; sz<s.length(); sz++) {
      |                ~~^~~~~~~~~~~
copypaste3.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=0; i<s.length()-sz; i++) {
      |                ~^~~~~~~~~~~~~~

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