Submission #565103

#	Time	Username	Problem	Language	Result	Execution time	Memory
565103		clarence	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	281 ms	34016 KiB

copypaste3

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int N;
char S[2510];
ll dp[2510][2510];
ll A, B, C;
int groups = 0;
int nextGroups = 0;
int counter[30];
vector<int> same[1500];
vector<int> same2[1500];
vector<int> temp[30];
int pow2[30];
int nextAnchor[2500];
int main(void) {
    for (int i=0;i<26;i++) {
        pow2[(1<<i)%29] = i;
    }
    scanf("%d %s%lld%lld%lld", &N, S, &A, &B, &C);
    for (int i=1;i<=N;i++) {
        for (int j=0;j+i<=N;j++) {
            dp[j][j+i] = A*i;
        }
    }
    for (int i=1;i<=N;i++) { // length
        for (int j=0;j+i<=N;j++) {
            dp[j][j+i] = min(dp[j][j+i], min(dp[j+1][j+i], dp[j][j+i-1])+A);
        }
        if (i<=N/2) {
            if (i == 1) {
                for (int j=0;j+i<=N;j++) {
                    temp[S[j]-'a'].push_back(j);
                }
                for (int k=0;k<26;k++) {
                    if ((int)temp[k].size()>=2) {
                        same[groups++] = temp[k];
                    }
                    temp[k].clear();
                }
            } else {
                // hash stuff??
                nextGroups = 0;
                int bm = 0;
                for (int k=0;k<groups;k++) {
                    for (int j=0;j<(int)same[k].size();j++) {
                        if (same[k][j]+i > N) continue;
                        bm = bm | (1 << (int)(S[same[k][j]+i-1]-'a'));
                        temp[S[same[k][j]+i-1]-'a'].push_back(same[k][j]);
                    }
                    // bitmask yay
                    while (bm) {
                        int lsb = bm & (-bm);
                        if (temp[pow2[lsb%29]].size() >= 2) {
                            same2[nextGroups++] = temp[pow2[lsb%29]];
                        }
                        temp[pow2[lsb%29]].clear();
                        bm -= lsb;
                    }
                }
                for (int k=0;k<nextGroups;k++) {
                    same[k] = same2[k];
                }
                groups = nextGroups;
            }
            for (int k=0;k<groups;k++) {
                int ptr = 0;
                int L = (int)same[k].size();
                for (int j=0;j<L;j++) {
                    // try making from here
                    // same[k] should be sorted
                    while (ptr < L && same[k][j]+i>same[k][ptr]) ptr++;
                    nextAnchor[j] = ptr;
                }
                ll dpValue = dp[same[k][0]][same[k][0]+i];
                for (int j=0;j<L;j++) {
                    // try making from here
                    // same[k] should be sorted
                    int cur = nextAnchor[j];
                    int cnt = 2;
                    int start = same[k][j];
                    while (cur < L) {
                        int stop = same[k][cur]+i;
                        dp[start][stop] = min(
                            dp[start][stop],
                            cnt * C + B + dpValue + A * (stop - start - cnt * i)
                        );
                        cur = nextAnchor[cur];
                        cnt++;
                    }
                }
            }
        }
    }
    /*for (int i=0;i<=N;i++) {
        for (int j=i;j<=N;j++) {
            printf("%lld ", dp[i][j]);
        } printf("\n");
    }*/
    printf("%lld\n", dp[0][N]);
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %s%lld%lld%lld", &N, S, &A, &B, &C);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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