oj.uz

Submission #843548

# Submission time Handle Problem Language Result Execution time Memory
843548 2023-09-04T04:49:22 Z Cookie Copy and Paste 3 (JOI22_copypaste3) C++14
0 / 100
 1 ms 4696 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>

const int mxn = 2505;
const ll inf = 1e18, mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rr(ll l, ll r){
    return(uniform_int_distribution<ll>(l, r)(rng));
}

ll n, a, b, c;
string s;
ll dp[mxn + 1][mxn + 1], hsh[mxn + 1], pw[mxn + 1];
int z[2505], nxt[2505][2505];
void ckmin(ll &a, ll b){
    a = min(a, b);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> a >> b >> c; 
    for(int i = 0; i < n; i++){
        int l = i, r = i;
        for(int j = i + 1; j < n; j++){
            if(j > r){
                l = r = j;
                while(r < n && s[r] == s[r - l + i])r++;
                z[j] = r - l; r--;
            }else{
                int pos = j - l;
                if(z[pos] < r - j + 1)z[j] = z[pos];
                else{
                    l = j;
                    while(r < n && s[r] == s[r - l + i])r++;
                    z[j] = r - l; r--;
                }
            }
        }
        int rp = i + 1;
        for(int j = 1; j <= n; j++){
            rp = max(rp, i + j);
            while(rp <= n && z[rp] < j){
                rp++;
            }
            if(rp <= n)nxt[i][j] = rp;
            else nxt[i][j] = -1;
        }
    }
    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 + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            ckmin(dp[l][r], dp[l + 1][r] + a); ckmin(dp[l][r], dp[l][r - 1] + a);
            
           
            int idl = l, cnt = 1;
            while(nxt[idl][len] != -1){
                idl = nxt[idl][len];
                cnt++;
                int nwr = idl + len - 1;
                ckmin(dp[l][nwr], dp[l][r] + b + c * cnt + a * (nwr - l + 1 - len * cnt));
            }
            
        }
        
    }
    cout << dp[1][n];
    return(0);
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -