제출 #1186138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186138		Gray	Copy and Paste 3 (JOI22_copypaste3)	C++20	25 / 100	3096 ms	26436 KiB

copypaste3

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

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

void solve(){
    ll n; cin >> n;
    string s; cin >> s;
    ll ca, cb, cc; cin >> ca >> cb >> cc;
    vector<vector<ll>> dp(n, vector<ll>(n));
    for (ll i=0; i<n; i++){
        dp[i][i]=ca;
    }
    for (ll i=1; i<n; i++){
        for (ll l=0, r=i; r<n; l++,r++){
            dp[l][r]=min(dp[l][r-1], dp[l+1][r])+ca;
            for (ll m=l; m<r; m++){
                ll rep=0;
                for (ll k=m; k<=r; k++){
                    bool pos=1;
                    for (ll mi=l, ki=k-(m-l+1)+1; mi<=m; mi++, ki++){
                        if (s[mi]!=s[ki]) pos=0;
                    }
                    if (pos) {
                        rep++; k+=(m-l+1); k--;
                    }
                }
                // if (rep>1) cout << l << " - " << r << " - " << m << ": " << rep << ln;
                dp[l][r]=min(dp[l][r], dp[l][m]+cb+cc*(rep)+ca*(r-l+1-(m-l+1)*(rep)));
            }
        }
    }
    cout << dp[0][n-1] << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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