Submission #788798

#	Time	Username	Problem	Language	Result	Execution time	Memory
788798		anhduc2701	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	374 ms	100784 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];
ll nxt[2505][2505];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    //freopen("friends.out","w",stdout);
    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++)
    {
        int l=i;
        for (int j = i; j < n; j++)
        {   
            if(l<=j) l=j+1;

            while(l<n && z[i][l]<j-i+1){

                l++;
            }
            nxt[i][j]=l;
            dp[i][j] = INF;
        }
    }
    
    for (int i = n - 1; i >= 0; i--)
    {
        dp[i][i] = A;
        for (int j = i; j < n; j++)
        {
            int len = j-i+1; 
            if(len>1){
                dp[i][j] = min({dp[i][j], dp[i + 1][j] + A, dp[i][j - 1] + A});
            }
            int last = i;
            int cnt=1;
            while(last<n){
                int r = nxt[last][last+len-1];
                
                if(r<n){
                    cnt++;
                    int en=r+len-1;
                    dp[i][en] = min(dp[i][en], dp[i][j] + B +  cnt * C + (en - i + 1 - cnt * len) * A);
                }
                
                last = r;
            }
        }
        // cout << "\n";
    }
    
    cout << dp[0][n - 1];
    
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:46: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]
   46 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
copypaste3.cpp:50: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]
   50 |         for (int j = i + 1; j < s.size(); j++)
      |                             ~~^~~~~~~~~~
copypaste3.cpp:56: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]
   56 |             while (j + z[i][j] < s.size() && s[j + z[i][j]] == s[i + z[i][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