제출 #776679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776679		danikoynov	Copy and Paste 3 (JOI22_copypaste3)	C++14	15 / 100	3064 ms	1108 KiB

copypaste3

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 210;
const ll base = 29, inf = 1e18;

int n;
ll a, b, c, h[maxn], pw[maxn], dp[maxn][maxn];
string s;
void solve()
{
    cin >> n >> s >> a >> b >> c;
    s = "#" + s;
    pw[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        h[i] = h[i - 1] * base + (s[i] - 'a' + 1);
        pw[i] = pw[i - 1] * base;
    }
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        dp[i][j] = inf;
    for (int len = 1; len <= n; len ++)
    for (int i = 1; i <= n - len + 1; i ++)
    {
        int j = i + len - 1;
        dp[i][j] = dp[i][j - 1] + a;

        for (int p = i; p <= j; p ++)
            for (int k = p; k <= j; k ++)
        {
                    ll clip_hash, clip_len = k - p + 1;
            clip_hash = h[k] - h[p - 1] * pw[clip_len];
            ll cost = dp[p][k] + b;
            int pos = i;
            while(pos <= j)
            {
                int to = pos + clip_len - 1;
                if (to > j)
                {
                    cost += (j - pos + 1) * a;
                    break;
                }
                if (h[to] - h[pos - 1] * pw[clip_len] == clip_hash)
                {
                    cost = cost + c;
                    pos = pos + clip_len;
                }
                else
                {
                    pos ++;
                    cost += a;
                }
            }
            dp[i][j] = min(dp[i][j], cost);
        }
    }

    cout << dp[1][n] << endl;


}

int main()
{
    solve();
    return 0;
}

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