oj.uz

Submission #544571

# Submission time Handle Problem Language Result Execution time Memory
544571 2022-04-02T11:19:33 Z Rafi22 Copy and Paste 3 (JOI22_copypaste3) C++14
100 / 100
 2229 ms 684156 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=2507;

ll DP[N][N];
int id[N][N];
int it;
set<int>V[N*N];
bool was[N*N];
int n;
string s;

void rek(vector<int>v,int l)
{
    vector<int>nx[26];
    if(l>0)
    {
        it++;
        V[it].insert(inf);
        for(auto x:v)
        {
            id[x][x+l-1]=it;
            V[it].insert(x);
        }
    }
    for(auto x:v)
    {
        if(x+l>n) continue;
        nx[s[x+l]-'a'].pb(x);
    }
    for(int i=0;i<26;i++) if(sz(nx[i])>0) rek(nx[i],l+1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll A,B,C;
    cin>>n>>s>>A>>B>>C;
    s='#'+s;
    for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) DP[i][j]=infl;
    for(int i=1;i<=n;i++) DP[i][i]=A;
    vector<int>v(n);
    for(int i=0;i<n;i++) v[i]=i+1;
    rek(v,0);
    for(int d=1;d<=n;d++)
    {
        for(int l=1;l+d-1<=n;l++)
        {
            int r=l+d-1;
            DP[l][r]=min({DP[l][r],DP[l+1][r]+A,DP[l][r-1]+A});
            int x=id[l][r];
            if(was[x]) continue;
            was[x]=1;
            while(sz(V[x])>1)
            {
                vector<int>P;
                int c=-inf;
                while(true)
                {
                    set<int>::iterator I=V[x].upper_bound(c);
                    if(*I==inf) break;
                    P.pb(*I);
                    c=*I+d-1;
                    V[x].erase(I);
                }
                for(int i=0;i<sz(P);i++)
                {
                    for(int j=i;j<sz(P);j++)
                    {
                        ll cost=B+(ll)(j-i+1)*C+(ll)(P[j]+d-P[i]-(j-i+1)*d)*A;
                        DP[P[i]][P[j]+d-1]=min(DP[P[i]][P[j]+d-1],DP[l][r]+cost);
                    }
                }
            }
        }
    }
    cout<<DP[1][n];
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 295456 KB Output is correct
2 Correct 127 ms 295524 KB Output is correct
3 Correct 127 ms 295480 KB Output is correct
4 Correct 133 ms 295544 KB Output is correct
5 Correct 127 ms 295640 KB Output is correct
6 Correct 129 ms 295468 KB Output is correct
7 Correct 127 ms 295504 KB Output is correct
8 Correct 125 ms 295492 KB Output is correct
9 Correct 127 ms 295500 KB Output is correct
10 Correct 125 ms 295444 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 295608 KB Output is correct
2 Correct 124 ms 295476 KB Output is correct
3 Correct 605 ms 438460 KB Output is correct
4 Correct 716 ms 460672 KB Output is correct
5 Correct 795 ms 484368 KB Output is correct
6 Correct 1024 ms 511392 KB Output is correct
7 Correct 1172 ms 542724 KB Output is correct
8 Correct 1163 ms 542752 KB Output is correct
9 Correct 1077 ms 542768 KB Output is correct
10 Correct 127 ms 295524 KB Output is correct
11 Correct 129 ms 295444 KB Output is correct
12 Correct 124 ms 295524 KB Output is correct
13 Correct 127 ms 295500 KB Output is correct
14 Correct 132 ms 295636 KB Output is correct
15 Correct 128 ms 295572 KB Output is correct
16 Correct 127 ms 295816 KB Output is correct
17 Correct 127 ms 295564 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 295456 KB Output is correct
2 Correct 127 ms 295524 KB Output is correct
3 Correct 127 ms 295480 KB Output is correct
4 Correct 133 ms 295544 KB Output is correct
5 Correct 127 ms 295640 KB Output is correct
6 Correct 129 ms 295468 KB Output is correct
7 Correct 127 ms 295504 KB Output is correct
8 Correct 125 ms 295492 KB Output is correct
9 Correct 127 ms 295500 KB Output is correct
10 Correct 125 ms 295444 KB Output is correct
11 Correct 127 ms 295664 KB Output is correct
12 Correct 131 ms 295664 KB Output is correct
13 Correct 124 ms 295640 KB Output is correct
14 Correct 125 ms 295596 KB Output is correct
15 Correct 133 ms 295688 KB Output is correct
16 Correct 127 ms 295628 KB Output is correct
17 Correct 129 ms 295540 KB Output is correct
18 Correct 150 ms 295428 KB Output is correct
19 Correct 131 ms 295596 KB Output is correct
20 Correct 128 ms 295556 KB Output is correct
21 Correct 130 ms 295808 KB Output is correct
22 Correct 130 ms 295772 KB Output is correct
23 Correct 128 ms 295840 KB Output is correct
24 Correct 128 ms 295808 KB Output is correct
25 Correct 131 ms 295760 KB Output is correct
26 Correct 132 ms 295764 KB Output is correct
27 Correct 127 ms 295756 KB Output is correct
28 Correct 131 ms 295824 KB Output is correct
29 Correct 124 ms 295752 KB Output is correct
30 Correct 126 ms 295780 KB Output is correct
31 Correct 127 ms 295756 KB Output is correct
32 Correct 124 ms 295768 KB Output is correct
33 Correct 129 ms 295904 KB Output is correct
34 Correct 125 ms 295452 KB Output is correct
35 Correct 126 ms 295404 KB Output is correct
36 Correct 134 ms 295556 KB Output is correct
37 Correct 129 ms 295516 KB Output is correct
38 Correct 128 ms 295628 KB Output is correct
39 Correct 123 ms 295820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 295456 KB Output is correct
2 Correct 127 ms 295524 KB Output is correct
3 Correct 127 ms 295480 KB Output is correct
4 Correct 133 ms 295544 KB Output is correct
5 Correct 127 ms 295640 KB Output is correct
6 Correct 129 ms 295468 KB Output is correct
7 Correct 127 ms 295504 KB Output is correct
8 Correct 125 ms 295492 KB Output is correct
9 Correct 127 ms 295500 KB Output is correct
10 Correct 125 ms 295444 KB Output is correct
11 Correct 127 ms 295664 KB Output is correct
12 Correct 131 ms 295664 KB Output is correct
13 Correct 124 ms 295640 KB Output is correct
14 Correct 125 ms 295596 KB Output is correct
15 Correct 133 ms 295688 KB Output is correct
16 Correct 127 ms 295628 KB Output is correct
17 Correct 129 ms 295540 KB Output is correct
18 Correct 150 ms 295428 KB Output is correct
19 Correct 131 ms 295596 KB Output is correct
20 Correct 128 ms 295556 KB Output is correct
21 Correct 130 ms 295808 KB Output is correct
22 Correct 130 ms 295772 KB Output is correct
23 Correct 128 ms 295840 KB Output is correct
24 Correct 128 ms 295808 KB Output is correct
25 Correct 131 ms 295760 KB Output is correct
26 Correct 132 ms 295764 KB Output is correct
27 Correct 127 ms 295756 KB Output is correct
28 Correct 131 ms 295824 KB Output is correct
29 Correct 124 ms 295752 KB Output is correct
30 Correct 126 ms 295780 KB Output is correct
31 Correct 127 ms 295756 KB Output is correct
32 Correct 124 ms 295768 KB Output is correct
33 Correct 129 ms 295904 KB Output is correct
34 Correct 125 ms 295452 KB Output is correct
35 Correct 126 ms 295404 KB Output is correct
36 Correct 134 ms 295556 KB Output is correct
37 Correct 129 ms 295516 KB Output is correct
38 Correct 128 ms 295628 KB Output is correct
39 Correct 123 ms 295820 KB Output is correct
40 Correct 126 ms 296588 KB Output is correct
41 Correct 132 ms 298896 KB Output is correct
42 Correct 134 ms 299568 KB Output is correct
43 Correct 132 ms 299576 KB Output is correct
44 Correct 131 ms 299596 KB Output is correct
45 Correct 134 ms 299608 KB Output is correct
46 Correct 136 ms 299596 KB Output is correct
47 Correct 134 ms 298880 KB Output is correct
48 Correct 138 ms 299164 KB Output is correct
49 Correct 135 ms 299352 KB Output is correct
50 Correct 133 ms 299248 KB Output is correct
51 Correct 129 ms 299084 KB Output is correct
52 Correct 132 ms 299108 KB Output is correct
53 Correct 131 ms 299572 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 295456 KB Output is correct
2 Correct 127 ms 295524 KB Output is correct
3 Correct 127 ms 295480 KB Output is correct
4 Correct 133 ms 295544 KB Output is correct
5 Correct 127 ms 295640 KB Output is correct
6 Correct 129 ms 295468 KB Output is correct
7 Correct 127 ms 295504 KB Output is correct
8 Correct 125 ms 295492 KB Output is correct
9 Correct 127 ms 295500 KB Output is correct
10 Correct 125 ms 295444 KB Output is correct
11 Correct 127 ms 295664 KB Output is correct
12 Correct 131 ms 295664 KB Output is correct
13 Correct 124 ms 295640 KB Output is correct
14 Correct 125 ms 295596 KB Output is correct
15 Correct 133 ms 295688 KB Output is correct
16 Correct 127 ms 295628 KB Output is correct
17 Correct 129 ms 295540 KB Output is correct
18 Correct 150 ms 295428 KB Output is correct
19 Correct 131 ms 295596 KB Output is correct
20 Correct 128 ms 295556 KB Output is correct
21 Correct 130 ms 295808 KB Output is correct
22 Correct 130 ms 295772 KB Output is correct
23 Correct 128 ms 295840 KB Output is correct
24 Correct 128 ms 295808 KB Output is correct
25 Correct 131 ms 295760 KB Output is correct
26 Correct 132 ms 295764 KB Output is correct
27 Correct 127 ms 295756 KB Output is correct
28 Correct 131 ms 295824 KB Output is correct
29 Correct 124 ms 295752 KB Output is correct
30 Correct 126 ms 295780 KB Output is correct
31 Correct 127 ms 295756 KB Output is correct
32 Correct 124 ms 295768 KB Output is correct
33 Correct 129 ms 295904 KB Output is correct
34 Correct 125 ms 295452 KB Output is correct
35 Correct 126 ms 295404 KB Output is correct
36 Correct 134 ms 295556 KB Output is correct
37 Correct 129 ms 295516 KB Output is correct
38 Correct 128 ms 295628 KB Output is correct
39 Correct 123 ms 295820 KB Output is correct
40 Correct 126 ms 296588 KB Output is correct
41 Correct 132 ms 298896 KB Output is correct
42 Correct 134 ms 299568 KB Output is correct
43 Correct 132 ms 299576 KB Output is correct
44 Correct 131 ms 299596 KB Output is correct
45 Correct 134 ms 299608 KB Output is correct
46 Correct 136 ms 299596 KB Output is correct
47 Correct 134 ms 298880 KB Output is correct
48 Correct 138 ms 299164 KB Output is correct
49 Correct 135 ms 299352 KB Output is correct
50 Correct 133 ms 299248 KB Output is correct
51 Correct 129 ms 299084 KB Output is correct
52 Correct 132 ms 299108 KB Output is correct
53 Correct 131 ms 299572 KB Output is correct
54 Correct 177 ms 310968 KB Output is correct
55 Correct 274 ms 342208 KB Output is correct
56 Correct 396 ms 363088 KB Output is correct
57 Correct 385 ms 363432 KB Output is correct
58 Correct 376 ms 363468 KB Output is correct
59 Correct 373 ms 363468 KB Output is correct
60 Correct 368 ms 363612 KB Output is correct
61 Correct 290 ms 349516 KB Output is correct
62 Correct 244 ms 339332 KB Output is correct
63 Correct 334 ms 357420 KB Output is correct
64 Correct 334 ms 357036 KB Output is correct
65 Correct 296 ms 350412 KB Output is correct
66 Correct 295 ms 350408 KB Output is correct
67 Correct 378 ms 363468 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 295456 KB Output is correct
2 Correct 127 ms 295524 KB Output is correct
3 Correct 127 ms 295480 KB Output is correct
4 Correct 133 ms 295544 KB Output is correct
5 Correct 127 ms 295640 KB Output is correct
6 Correct 129 ms 295468 KB Output is correct
7 Correct 127 ms 295504 KB Output is correct
8 Correct 125 ms 295492 KB Output is correct
9 Correct 127 ms 295500 KB Output is correct
10 Correct 125 ms 295444 KB Output is correct
11 Correct 129 ms 295608 KB Output is correct
12 Correct 124 ms 295476 KB Output is correct
13 Correct 605 ms 438460 KB Output is correct
14 Correct 716 ms 460672 KB Output is correct
15 Correct 795 ms 484368 KB Output is correct
16 Correct 1024 ms 511392 KB Output is correct
17 Correct 1172 ms 542724 KB Output is correct
18 Correct 1163 ms 542752 KB Output is correct
19 Correct 1077 ms 542768 KB Output is correct
20 Correct 127 ms 295524 KB Output is correct
21 Correct 129 ms 295444 KB Output is correct
22 Correct 124 ms 295524 KB Output is correct
23 Correct 127 ms 295500 KB Output is correct
24 Correct 132 ms 295636 KB Output is correct
25 Correct 128 ms 295572 KB Output is correct
26 Correct 127 ms 295816 KB Output is correct
27 Correct 127 ms 295564 KB Output is correct
28 Correct 127 ms 295664 KB Output is correct
29 Correct 131 ms 295664 KB Output is correct
30 Correct 124 ms 295640 KB Output is correct
31 Correct 125 ms 295596 KB Output is correct
32 Correct 133 ms 295688 KB Output is correct
33 Correct 127 ms 295628 KB Output is correct
34 Correct 129 ms 295540 KB Output is correct
35 Correct 150 ms 295428 KB Output is correct
36 Correct 131 ms 295596 KB Output is correct
37 Correct 128 ms 295556 KB Output is correct
38 Correct 130 ms 295808 KB Output is correct
39 Correct 130 ms 295772 KB Output is correct
40 Correct 128 ms 295840 KB Output is correct
41 Correct 128 ms 295808 KB Output is correct
42 Correct 131 ms 295760 KB Output is correct
43 Correct 132 ms 295764 KB Output is correct
44 Correct 127 ms 295756 KB Output is correct
45 Correct 131 ms 295824 KB Output is correct
46 Correct 124 ms 295752 KB Output is correct
47 Correct 126 ms 295780 KB Output is correct
48 Correct 127 ms 295756 KB Output is correct
49 Correct 124 ms 295768 KB Output is correct
50 Correct 129 ms 295904 KB Output is correct
51 Correct 125 ms 295452 KB Output is correct
52 Correct 126 ms 295404 KB Output is correct
53 Correct 134 ms 295556 KB Output is correct
54 Correct 129 ms 295516 KB Output is correct
55 Correct 128 ms 295628 KB Output is correct
56 Correct 123 ms 295820 KB Output is correct
57 Correct 126 ms 296588 KB Output is correct
58 Correct 132 ms 298896 KB Output is correct
59 Correct 134 ms 299568 KB Output is correct
60 Correct 132 ms 299576 KB Output is correct
61 Correct 131 ms 299596 KB Output is correct
62 Correct 134 ms 299608 KB Output is correct
63 Correct 136 ms 299596 KB Output is correct
64 Correct 134 ms 298880 KB Output is correct
65 Correct 138 ms 299164 KB Output is correct
66 Correct 135 ms 299352 KB Output is correct
67 Correct 133 ms 299248 KB Output is correct
68 Correct 129 ms 299084 KB Output is correct
69 Correct 132 ms 299108 KB Output is correct
70 Correct 131 ms 299572 KB Output is correct
71 Correct 177 ms 310968 KB Output is correct
72 Correct 274 ms 342208 KB Output is correct
73 Correct 396 ms 363088 KB Output is correct
74 Correct 385 ms 363432 KB Output is correct
75 Correct 376 ms 363468 KB Output is correct
76 Correct 373 ms 363468 KB Output is correct
77 Correct 368 ms 363612 KB Output is correct
78 Correct 290 ms 349516 KB Output is correct
79 Correct 244 ms 339332 KB Output is correct
80 Correct 334 ms 357420 KB Output is correct
81 Correct 334 ms 357036 KB Output is correct
82 Correct 296 ms 350412 KB Output is correct
83 Correct 295 ms 350408 KB Output is correct
84 Correct 378 ms 363468 KB Output is correct
85 Correct 768 ms 458220 KB Output is correct
86 Correct 1842 ms 683052 KB Output is correct
87 Correct 1821 ms 683064 KB Output is correct
88 Correct 1821 ms 683612 KB Output is correct
89 Correct 1881 ms 683852 KB Output is correct
90 Correct 1850 ms 683836 KB Output is correct
91 Correct 850 ms 523100 KB Output is correct
92 Correct 923 ms 518024 KB Output is correct
93 Correct 1622 ms 636572 KB Output is correct
94 Correct 1814 ms 637532 KB Output is correct
95 Correct 1709 ms 592020 KB Output is correct
96 Correct 1612 ms 592036 KB Output is correct
97 Correct 2229 ms 684156 KB Output is correct