Submission #788770

#	Time	Username	Problem	Language	Result	Execution time	Memory
788770		anhduc2701	Copy and Paste 3 (JOI22_copypaste3)	C++17	1 / 100	109 ms	54232 KiB

copypaste3

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll n;
string s;
ll A, B, C;
ll z[2505][2505];
ll dp[2505][2505];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    cin >> A >> B >> C;
    for (int i = 0; i < s.size(); i++)
    {
        int l = i;
        int r = i;
        for (int j = i + 1; j < s.size(); j++)
        {
            if (j < r)
            {
                z[i][j] = min(z[i][j - l + i], r - j);
            }
            while (j + z[i][j] < s.size() && s[j + z[i][j]] == s[i + z[i][j]])
            {
                z[i][j]++;
            }
            if (r < j + z[i][j])
            {
                l = j;
                r = j + z[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i][j] = INF;
        }
    }
    for (int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = A;
        vector<int> pos;
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] == s[j])
            {
                pos.pb(j);
                dp[i][j] = min(dp[i][j], dp[i][i] + B + (len(pos) + 1) * C + (j - i + 1 - (len(pos) + 1)) * A);
            }
        }
        for (int j = i + 1; j < n; j++)
        {
            vector<int> re;
            dp[i][j] = min({dp[i][j], dp[i + 1][j] + A, dp[i][j - 1] + A});
            int last = j;
            for (auto v : pos)
            {
                if (last < v && z[i][v] >= j - i + 1)
                {
                    int r = v + j - i;
                    re.pb(v);
                    dp[i][r] = min(dp[i][r], dp[i][j] + B + (len(re) + 1) * C + (r - i + 1 - (len(re) + 1) * (j - i + 1)) * A);
                    last = r;
                }
            }
            pos.swap(re);
        }
    }
    cout << dp[0][n - 1];
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:44:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
copypaste3.cpp:48:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int j = i + 1; j < s.size(); j++)
      |                             ~~^~~~~~~~~~
copypaste3.cpp:54:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while (j + z[i][j] < s.size() && s[j + z[i][j]] == s[i + z[i][j]])
      |                    ~~~~~~~~~~~~^~~~~~~~~~

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