Submission #795022

#	Time	Username	Problem	Language	Result	Execution time	Memory
795022		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	351 ms	54068 KiB

copypaste3

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 2505;
const int mod = 1e9 + 7;

using namespace std;

vector<int> z_function(string s) {
	vector<int> z(s.size());
	for (int i = 1, l = 0, r = 0; i < s.size(); i++) {
        if (i <= r) {
            z[i] = min(r - i, z[i - l]);
        }
        while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
	}
	return z;
}

int n;
string s;
int z[N][N];
long long A, B, C;
long long d[N][N];
long long inf = 1e18;

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n >> s >> A >> B >> C;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            z[i][j] = n;
            d[i][j] = inf;
        }
        auto g = z_function(s.substr(i));
        for (int j = 1; j < g.size(); j++) {
            if (g[j] == 0) {
                continue;
            }
            int h = i + min(j, g[j]) - 1;
            z[i][h] = min(z[i][h], i + j);
        }
        for (int j = n - 1; j > i; j--) {
            z[i][j - 1] = min(z[i][j - 1], z[i][j]);
        }
    }
    cin >> A >> B >> C;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            d[i][j] = min(d[i][j], min(d[i + 1][j], d[i][j - 1]) + A);

            int x = i, cnt = 0;
            while (z[x][x + j - i] != n) {
                cnt += 1;
                int y = z[x][x + j - i];
                d[i][y + j - i] = min(d[i][y + j - i], d[i][j] + B + C * (cnt + 1) + A * (y - j - 1 - (j - i + 1) * (cnt - 1)));
                x = y;
            }
        }
    }

    cout << d[0][n - 1] << "\n";
}

Compilation message (stderr)

copypaste3.cpp: In function 'std::vector<int> z_function(std::string)':
copypaste3.cpp:13:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 1, l = 0, r = 0; i < s.size(); i++) {
      |                                ~~^~~~~~~~~~
copypaste3.cpp:17:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) {
      |                ~~~~~~~~~^~~~~~~~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 1; j < g.size(); j++) {
      |                         ~~^~~~~~~~~~

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