Submission #1177144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177144		AlperenT_	Copy and Paste 3 (JOI22_copypaste3)	C++20	57 / 100	1442 ms	493848 KiB

copypaste3

#include <bits/stdc++.h>

#define pb push_back
#define int long long 
#define F first
#define S second
#define sz(a) (int)a.size()
#define pii pair<int,int> 
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define all(a) a.begin(),a.end() 

using namespace std ;
const int maxn = 2600 , mod = 1e9 + 7;
vector <pii> vec[maxn][maxn] ;
vector <int> v[maxn] ;
int par[maxn] ;

int dp[maxn][maxn] , z[maxn] ;

int find(int v){
    if(par[v] == v)return v;
    return par[v] = find(par[v]); 
}

void mrg(int v, int u){
    v = find(v) ;
    u = find(u) ;
    if(v==u)return ;
    par[v] = u ; 
}
signed main(){
    ios::sync_with_stdio(0) ; cin.tie(0);
    int n;cin >> n ;
    string s;
    cin >> s; 
    s= " " + s  ;
    int a,  b, c;
    cin >> a >> b >> c; 
    rep(i , 1, n){
        string t ;; 
        rep(j ,i ,n){
            t += s[j];  
        }
        int len = n-i+1 ;
        int l =0 , r =0 ;
        rep(i , 0 , len)v[i].clear() ;
        rep(j , 0, len-1){
            z[j]= 0 ;
            if(j < r){
                z[j] = min(r-j , z[j-l]) ;
            }
            while(j+z[j] < len && t[j+z[j]] == t[z[j]])z[j]++;
            if(r < j+z[j]){
                l = j;
                r = z[j]+j ; 
            }
            v[z[j]].pb(j) ;
        }
        rep(i ,0 , len)par[i] = i ;
        rep(j , 1 , len-1){
            for(int x : v[j-1]){
                mrg(x , x+1) ;
            }
            int st = 0 , ted =0  ;
            while(st < len){
                st = find(st) ; 
                ted++ ;
          //      cout << i << " " << i+st+j-1 << " : " << j  << " " << ted << "<--\n"; 
                vec[i][i+st+j-1].pb({ted , j});
                st+=j ;
            }
        }

    }
    rep(len , 1, n){
        for(int l =1 , r= len ; r <= n ; r++,l++){
            dp[l][r] = a+ min(dp[l+1][r] , dp[l][r-1]) ;
            for(auto [t , s] : vec[l][r]){
                dp[l][r] = min(dp[l][r] , dp[l][l+s-1] + b + c*t + a * (len-t*s)) ; 
            }
        }
    }
    cout << dp[1][n] << "\n"; 
}

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