제출 #776841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776841		danikoynov	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	2519 ms	517672 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 = 2510;
const ll base = 29, inf = 1e18;

int n;
ll a, b, c, h[maxn], pw[maxn];
string s;
vector < int >  occ[maxn * maxn];
ll hs_dp[maxn * maxn], pt[maxn * maxn];
int nxt[maxn][maxn];

ll range_hash[maxn][maxn];
ll get_hash(int i, int j)
{
    return range_hash[i][j];
}

unordered_map < ll, ll > rev;
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;
    }
    vector < ll > cp;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        {
            range_hash[i][j] = h[j] - h[i - 1] * pw[j - i + 1];
            cp.push_back(range_hash[i][j]);
        }
    ///cp.erase(unique(cp.begin(), cp.end()), cp.end());
    ///sort(cp.begin(), cp.end());
    int cnt = 0;
    for (int i = 0; i < cp.size(); i ++)
    {
        if (rev[cp[i]] == 0)
        rev[cp[i]] = i + 1;
    }

    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
            range_hash[i][j] = rev[range_hash[i][j]];


    for (int i = n; i > 0; i --)
    {

            ////cout << "------------" << endl;
        for (int p = i; p <= n; p ++)
        {
            int cur_hs = range_hash[i][p];
            occ[cur_hs].push_back(i);
            /**cout << "hash " << i << " " << p << endl;
            cout << "occurrences: ";
            for (int ds : occ[cur_hs])
                cout << ds << " ";
            cout << endl;*/
            if (occ[cur_hs].size() == 1)
            {
                hs_dp[cur_hs] = hs_dp[range_hash[i + 1][p]] + a;

                nxt[p - i + 1][p] = n + 1;
                pt[cur_hs] = -1;
            }
            else
            {
                hs_dp[cur_hs] = min(hs_dp[cur_hs], hs_dp[range_hash[i + 1][p]] + a);
                if (pt[cur_hs] == -1)
                {
                    pt[cur_hs] ++;
                }
                while(occ[cur_hs][pt[cur_hs]] > p)
                    pt[cur_hs] ++;
                pt[cur_hs] --;
                ///cout << i << endl;
                if (pt[cur_hs] == -1)
                    nxt[p - i + 1][p] = n + 1;
                else
                    nxt[p - i + 1][p] = occ[cur_hs][pt[cur_hs]] + (p - i);
            ///cout << "step " << i << " " << p << " " << nxt[p - i + 1][p] << endl;
            }
        }



        for (int k = i; k <= n; k ++)
        {
            int clip_hash, clip_len = k - i + 1;
            clip_hash = get_hash(i, k);
            ll cost = hs_dp[clip_hash] + b + c;

            if (occ[get_hash(i, k)].size() < 2)
                break;
            int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
            ///dp[get_hash(i, k)] = min(dp[get_hash(i, k)], cos);
            //cout << "-------------------" << endl;
            ///cout << i << " " << k << endl;
            while(pos <= n)
            {
                //cout << pos << " " << cost << endl;
                int to = nxt[clip_len][pos];
                if (to > n)
                    break;
                cost = cost + (to - pos - clip_len) * a;
                cost = cost + c;
                ///cout << "stop " << occ[clip_hash][pt] << endl;
                ///cost = cost + (occ[clip_hash][pt] - pos) * a;
                ///cost = cost + c;
                pos = to;
                hs_dp[range_hash[i][pos]] = min(hs_dp[range_hash[i][pos]], cost);

                /**int to = pos + clip_len - 1;

                if (to > n)
                {
                    break;
                }

                if (get_hash(pos, to) == clip_hash)
                {

                    cost = cost + c;
                    pos = pos + clip_len;
                    hs_dp[get_hash(i, to)] = min(hs_dp[get_hash(i, to)], cost);
                }
                else
                {
                    pos ++;
                    cost += a;
                }*/
            }

        }
        for (int k = i; k <= n; k ++)
        {
            hs_dp[range_hash[i][k]] = min(hs_dp[range_hash[i][k]], hs_dp[range_hash[i][k - 1]] + a);
        }

    }

    /**for (int i = 1; i <= n; i ++, cout << endl)
        for (int j = i; j <= n; j ++)
            cout << hs_dp[get_hash(i, j)] << " ";*/

    cout << hs_dp[range_hash[1][n]] << endl;


}

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

컴파일 시 표준 에러 (stderr) 메시지

copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < cp.size(); i ++)
      |                     ~~^~~~~~~~~~~
copypaste3.cpp:120:26: warning: unused variable 'pt' [-Wunused-variable]
  120 |             int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
      |                          ^~
copypaste3.cpp:59:9: warning: unused variable 'cnt' [-Wunused-variable]
   59 |     int cnt = 0;
      |         ^~~

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