Submission #1136560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136560		mariaclara	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	375 ms	50152 KiB

copypaste3

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 5e5+5;
const ll MOD = 1e9+7;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, nxt[2505][2505];
string s;
ll dp[2505][2505], A, B, C;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s >> A >> B >> C;

    vector<vector<int>> group(1);

    for(int i = 0; i < n; i++)
        group[0].pb(i);

    for(int len = 0; len < n; len++) {
        vector<vector<int>> at_group;

        for(int G = 0; G < sz(group); G++) {
            vector<int> letter[26];

            for(int i : group[G])
                if(i + len < n) letter[s[i + len] - 'a'].pb(i);

            for(int l = 0; l < 26; l++)
                if(!letter[l].empty()) at_group.pb(letter[l]);
        }

        group = at_group;

        for(int G = 0; G < sz(group); G++) {
            if(sz(group[G]) == 1) continue;

            for(int i = 0, j = 0; i < sz(group[G]); i++) {
                while(j < sz(group[G]) and group[G][j] <= group[G][i] + len) j++;
                if(j == sz(group[G])) break;

                nxt[group[G][i]][group[G][i] + len] = group[G][j] + len;
            }
        } 
    }

    // set dp
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            dp[i][j] = A*(j-i+1);

    // calcular dp
    for(int len = 0; len < n; len++) {
        for(int i = 0, j = len; j < n; i++, j++) {
            if(len) dp[i][j] = min({dp[i][j], dp[i+1][j] + A, dp[i][j-1] + A});

            // vamos olhar para as dps que podem ser formadas usando (i, j)

            for(int k = nxt[i][j], cnt = 2; k != 0; k = nxt[k - len][k], cnt++)
                dp[i][k] = min(dp[i][k], dp[i][j] + B + cnt*C + (k-i+1 - cnt*len - cnt)*A);
        }
    }

    cout << dp[0][n-1];
}

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