oj.uz

Submission #904761

# Submission time Handle Problem Language Result Execution time Memory
904761 2024-01-12T08:12:57 Z Tuanlinh123 Copy and Paste 3 (JOI22_copypaste3) C++17
30 / 100
 3000 ms 324076 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll p=31, maxn=2505;
const long long Mod=1e9+7;
vector <ll> pos[maxn*maxn];
long long Hash[maxn][maxn], check[maxn*maxn];
ll pi[maxn][maxn], idx[maxn][maxn], cnt[maxn][maxn], R[maxn][maxn];

inline ll calc(ll l, ll r, ll q)
{
    ll id=idx[l][r], len=r-l+1;
    while (1)
    {
        ll p=upper_bound(pos[id].begin(), pos[id].end(), R[l][r])-pos[id].begin();
        if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
        cnt[l][r]++, R[l][r]=pos[id][p]+len-1;
    }
    return cnt[l][r];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    string s; cin >> s; s='$'+s;
    long long A, B, C; cin >> A >> B >> C;
    vector <long long> num;
    for (ll i=1; i<=n; i++)
    {
        for (ll j=i+1; j<=n; j++)
        {
            ll k=pi[i][j-1];
            while (k && s[i+k]!=s[j])
                k=pi[i][k-1];
            pi[i][j]=k+(s[i+k]==s[j]);
        }
        for (ll j=i; j<=n; j++)
        {
            Hash[i][j]=(Hash[i][j-1]*p+s[j]-'a'+1)%Mod;
            num.pb(Hash[i][j]), R[i][j]=j, cnt[i][j]=1;
        }
    }
    sort(num.begin(), num.end());
    num.resize(unique(num.begin(), num.end())-num.begin());
    for (ll i=1; i<=n; i++)
        for (ll j=i; j<=n; j++)
        {
            idx[i][j]=lower_bound(num.begin(), num.end(), Hash[i][j])-num.begin();
            pos[idx[i][j]].pb(i);
        }
    for (ll len=1; len<=n; len++)
    {
        for (ll i=1; i+len<=n+1; i++)
        {
            ll j=i+len-1, crr=pi[i][j];
            if (check[idx[i][j]])
                continue;
            check[idx[i][j]]=A*len;
            if (i<j) check[idx[i][j]]=min({check[idx[i][j]], check[idx[i+1][j]]+A, check[idx[i][j-1]]+A});
            for (ll k=i; k<j; k++)
            {
                ll crr=k-i+1, c=calc(i, i+crr-1, j);
                long long val=check[idx[i][i+crr-1]];
                check[idx[i][j]]=min(check[idx[i][j]], val+B+C*c+A*(len-crr*c));
            }
        }
    }
    cout << check[idx[1][n]];
}

Compilation message

copypaste3.cpp: In function 'int calc(int, int, int)':
copypaste3.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
      |             ~^~~~~~~~~~~~~~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:66:27: warning: unused variable 'crr' [-Wunused-variable]
   66 |             ll j=i+len-1, crr=pi[i][j];
      |                           ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153072 KB Output is correct
2 Correct 56 ms 153172 KB Output is correct
3 Correct 55 ms 153316 KB Output is correct
4 Correct 57 ms 153164 KB Output is correct
5 Correct 55 ms 153172 KB Output is correct
6 Correct 59 ms 153256 KB Output is correct
7 Correct 55 ms 153172 KB Output is correct
8 Correct 55 ms 153172 KB Output is correct
9 Correct 56 ms 153172 KB Output is correct
10 Correct 56 ms 153172 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 153428 KB Output is correct
2 Correct 59 ms 153144 KB Output is correct
3 Correct 602 ms 271604 KB Output is correct
4 Correct 456 ms 286372 KB Output is correct
5 Correct 491 ms 302556 KB Output is correct
6 Correct 560 ms 313000 KB Output is correct
7 Correct 708 ms 323744 KB Output is correct
8 Correct 694 ms 324076 KB Output is correct
9 Correct 671 ms 322992 KB Output is correct
10 Correct 56 ms 153288 KB Output is correct
11 Correct 57 ms 153172 KB Output is correct
12 Correct 59 ms 153196 KB Output is correct
13 Correct 57 ms 153180 KB Output is correct
14 Correct 57 ms 153620 KB Output is correct
15 Correct 61 ms 153344 KB Output is correct
16 Correct 58 ms 157544 KB Output is correct
17 Correct 55 ms 153112 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153072 KB Output is correct
2 Correct 56 ms 153172 KB Output is correct
3 Correct 55 ms 153316 KB Output is correct
4 Correct 57 ms 153164 KB Output is correct
5 Correct 55 ms 153172 KB Output is correct
6 Correct 59 ms 153256 KB Output is correct
7 Correct 55 ms 153172 KB Output is correct
8 Correct 55 ms 153172 KB Output is correct
9 Correct 56 ms 153172 KB Output is correct
10 Correct 56 ms 153172 KB Output is correct
11 Correct 59 ms 153436 KB Output is correct
12 Correct 56 ms 153476 KB Output is correct
13 Correct 56 ms 155552 KB Output is correct
14 Correct 59 ms 153376 KB Output is correct
15 Correct 59 ms 155564 KB Output is correct
16 Correct 59 ms 153428 KB Output is correct
17 Correct 58 ms 153260 KB Output is correct
18 Correct 56 ms 153284 KB Output is correct
19 Correct 56 ms 153436 KB Output is correct
20 Correct 56 ms 153180 KB Output is correct
21 Correct 60 ms 157524 KB Output is correct
22 Correct 56 ms 157524 KB Output is correct
23 Correct 58 ms 157672 KB Output is correct
24 Correct 57 ms 157524 KB Output is correct
25 Correct 67 ms 157580 KB Output is correct
26 Correct 58 ms 157724 KB Output is correct
27 Correct 60 ms 157584 KB Output is correct
28 Correct 57 ms 157532 KB Output is correct
29 Correct 56 ms 157524 KB Output is correct
30 Correct 57 ms 157524 KB Output is correct
31 Correct 56 ms 157708 KB Output is correct
32 Correct 57 ms 157524 KB Output is correct
33 Correct 57 ms 157492 KB Output is correct
34 Correct 58 ms 153288 KB Output is correct
35 Correct 59 ms 153276 KB Output is correct
36 Correct 60 ms 153124 KB Output is correct
37 Correct 57 ms 153172 KB Output is correct
38 Correct 55 ms 153432 KB Output is correct
39 Correct 57 ms 157532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153072 KB Output is correct
2 Correct 56 ms 153172 KB Output is correct
3 Correct 55 ms 153316 KB Output is correct
4 Correct 57 ms 153164 KB Output is correct
5 Correct 55 ms 153172 KB Output is correct
6 Correct 59 ms 153256 KB Output is correct
7 Correct 55 ms 153172 KB Output is correct
8 Correct 55 ms 153172 KB Output is correct
9 Correct 56 ms 153172 KB Output is correct
10 Correct 56 ms 153172 KB Output is correct
11 Correct 59 ms 153436 KB Output is correct
12 Correct 56 ms 153476 KB Output is correct
13 Correct 56 ms 155552 KB Output is correct
14 Correct 59 ms 153376 KB Output is correct
15 Correct 59 ms 155564 KB Output is correct
16 Correct 59 ms 153428 KB Output is correct
17 Correct 58 ms 153260 KB Output is correct
18 Correct 56 ms 153284 KB Output is correct
19 Correct 56 ms 153436 KB Output is correct
20 Correct 56 ms 153180 KB Output is correct
21 Correct 60 ms 157524 KB Output is correct
22 Correct 56 ms 157524 KB Output is correct
23 Correct 58 ms 157672 KB Output is correct
24 Correct 57 ms 157524 KB Output is correct
25 Correct 67 ms 157580 KB Output is correct
26 Correct 58 ms 157724 KB Output is correct
27 Correct 60 ms 157584 KB Output is correct
28 Correct 57 ms 157532 KB Output is correct
29 Correct 56 ms 157524 KB Output is correct
30 Correct 57 ms 157524 KB Output is correct
31 Correct 56 ms 157708 KB Output is correct
32 Correct 57 ms 157524 KB Output is correct
33 Correct 57 ms 157492 KB Output is correct
34 Correct 58 ms 153288 KB Output is correct
35 Correct 59 ms 153276 KB Output is correct
36 Correct 60 ms 153124 KB Output is correct
37 Correct 57 ms 153172 KB Output is correct
38 Correct 55 ms 153432 KB Output is correct
39 Correct 57 ms 157532 KB Output is correct
40 Correct 62 ms 160400 KB Output is correct
41 Correct 63 ms 161564 KB Output is correct
42 Correct 78 ms 162136 KB Output is correct
43 Correct 76 ms 162056 KB Output is correct
44 Correct 73 ms 162264 KB Output is correct
45 Correct 76 ms 162264 KB Output is correct
46 Correct 74 ms 162264 KB Output is correct
47 Correct 68 ms 161752 KB Output is correct
48 Correct 71 ms 161752 KB Output is correct
49 Correct 74 ms 162008 KB Output is correct
50 Correct 73 ms 162100 KB Output is correct
51 Correct 74 ms 161884 KB Output is correct
52 Correct 75 ms 162016 KB Output is correct
53 Correct 73 ms 162176 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153072 KB Output is correct
2 Correct 56 ms 153172 KB Output is correct
3 Correct 55 ms 153316 KB Output is correct
4 Correct 57 ms 153164 KB Output is correct
5 Correct 55 ms 153172 KB Output is correct
6 Correct 59 ms 153256 KB Output is correct
7 Correct 55 ms 153172 KB Output is correct
8 Correct 55 ms 153172 KB Output is correct
9 Correct 56 ms 153172 KB Output is correct
10 Correct 56 ms 153172 KB Output is correct
11 Correct 59 ms 153436 KB Output is correct
12 Correct 56 ms 153476 KB Output is correct
13 Correct 56 ms 155552 KB Output is correct
14 Correct 59 ms 153376 KB Output is correct
15 Correct 59 ms 155564 KB Output is correct
16 Correct 59 ms 153428 KB Output is correct
17 Correct 58 ms 153260 KB Output is correct
18 Correct 56 ms 153284 KB Output is correct
19 Correct 56 ms 153436 KB Output is correct
20 Correct 56 ms 153180 KB Output is correct
21 Correct 60 ms 157524 KB Output is correct
22 Correct 56 ms 157524 KB Output is correct
23 Correct 58 ms 157672 KB Output is correct
24 Correct 57 ms 157524 KB Output is correct
25 Correct 67 ms 157580 KB Output is correct
26 Correct 58 ms 157724 KB Output is correct
27 Correct 60 ms 157584 KB Output is correct
28 Correct 57 ms 157532 KB Output is correct
29 Correct 56 ms 157524 KB Output is correct
30 Correct 57 ms 157524 KB Output is correct
31 Correct 56 ms 157708 KB Output is correct
32 Correct 57 ms 157524 KB Output is correct
33 Correct 57 ms 157492 KB Output is correct
34 Correct 58 ms 153288 KB Output is correct
35 Correct 59 ms 153276 KB Output is correct
36 Correct 60 ms 153124 KB Output is correct
37 Correct 57 ms 153172 KB Output is correct
38 Correct 55 ms 153432 KB Output is correct
39 Correct 57 ms 157532 KB Output is correct
40 Correct 62 ms 160400 KB Output is correct
41 Correct 63 ms 161564 KB Output is correct
42 Correct 78 ms 162136 KB Output is correct
43 Correct 76 ms 162056 KB Output is correct
44 Correct 73 ms 162264 KB Output is correct
45 Correct 76 ms 162264 KB Output is correct
46 Correct 74 ms 162264 KB Output is correct
47 Correct 68 ms 161752 KB Output is correct
48 Correct 71 ms 161752 KB Output is correct
49 Correct 74 ms 162008 KB Output is correct
50 Correct 73 ms 162100 KB Output is correct
51 Correct 74 ms 161884 KB Output is correct
52 Correct 75 ms 162016 KB Output is correct
53 Correct 73 ms 162176 KB Output is correct
54 Correct 245 ms 179920 KB Output is correct
55 Correct 125 ms 209244 KB Output is correct
56 Execution timed out 3044 ms 225736 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 153072 KB Output is correct
2 Correct 56 ms 153172 KB Output is correct
3 Correct 55 ms 153316 KB Output is correct
4 Correct 57 ms 153164 KB Output is correct
5 Correct 55 ms 153172 KB Output is correct
6 Correct 59 ms 153256 KB Output is correct
7 Correct 55 ms 153172 KB Output is correct
8 Correct 55 ms 153172 KB Output is correct
9 Correct 56 ms 153172 KB Output is correct
10 Correct 56 ms 153172 KB Output is correct
11 Correct 57 ms 153428 KB Output is correct
12 Correct 59 ms 153144 KB Output is correct
13 Correct 602 ms 271604 KB Output is correct
14 Correct 456 ms 286372 KB Output is correct
15 Correct 491 ms 302556 KB Output is correct
16 Correct 560 ms 313000 KB Output is correct
17 Correct 708 ms 323744 KB Output is correct
18 Correct 694 ms 324076 KB Output is correct
19 Correct 671 ms 322992 KB Output is correct
20 Correct 56 ms 153288 KB Output is correct
21 Correct 57 ms 153172 KB Output is correct
22 Correct 59 ms 153196 KB Output is correct
23 Correct 57 ms 153180 KB Output is correct
24 Correct 57 ms 153620 KB Output is correct
25 Correct 61 ms 153344 KB Output is correct
26 Correct 58 ms 157544 KB Output is correct
27 Correct 55 ms 153112 KB Output is correct
28 Correct 59 ms 153436 KB Output is correct
29 Correct 56 ms 153476 KB Output is correct
30 Correct 56 ms 155552 KB Output is correct
31 Correct 59 ms 153376 KB Output is correct
32 Correct 59 ms 155564 KB Output is correct
33 Correct 59 ms 153428 KB Output is correct
34 Correct 58 ms 153260 KB Output is correct
35 Correct 56 ms 153284 KB Output is correct
36 Correct 56 ms 153436 KB Output is correct
37 Correct 56 ms 153180 KB Output is correct
38 Correct 60 ms 157524 KB Output is correct
39 Correct 56 ms 157524 KB Output is correct
40 Correct 58 ms 157672 KB Output is correct
41 Correct 57 ms 157524 KB Output is correct
42 Correct 67 ms 157580 KB Output is correct
43 Correct 58 ms 157724 KB Output is correct
44 Correct 60 ms 157584 KB Output is correct
45 Correct 57 ms 157532 KB Output is correct
46 Correct 56 ms 157524 KB Output is correct
47 Correct 57 ms 157524 KB Output is correct
48 Correct 56 ms 157708 KB Output is correct
49 Correct 57 ms 157524 KB Output is correct
50 Correct 57 ms 157492 KB Output is correct
51 Correct 58 ms 153288 KB Output is correct
52 Correct 59 ms 153276 KB Output is correct
53 Correct 60 ms 153124 KB Output is correct
54 Correct 57 ms 153172 KB Output is correct
55 Correct 55 ms 153432 KB Output is correct
56 Correct 57 ms 157532 KB Output is correct
57 Correct 62 ms 160400 KB Output is correct
58 Correct 63 ms 161564 KB Output is correct
59 Correct 78 ms 162136 KB Output is correct
60 Correct 76 ms 162056 KB Output is correct
61 Correct 73 ms 162264 KB Output is correct
62 Correct 76 ms 162264 KB Output is correct
63 Correct 74 ms 162264 KB Output is correct
64 Correct 68 ms 161752 KB Output is correct
65 Correct 71 ms 161752 KB Output is correct
66 Correct 74 ms 162008 KB Output is correct
67 Correct 73 ms 162100 KB Output is correct
68 Correct 74 ms 161884 KB Output is correct
69 Correct 75 ms 162016 KB Output is correct
70 Correct 73 ms 162176 KB Output is correct
71 Correct 245 ms 179920 KB Output is correct
72 Correct 125 ms 209244 KB Output is correct
73 Execution timed out 3044 ms 225736 KB Time limit exceeded
74 Halted 0 ms 0 KB -