QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#24360	#562. 码农	mrkhkaw	100 ✓	13ms	18924kb	C++20	1.9kb	2022-03-30 02:43:50	2022-04-30 05:30:14

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-04-30 05:30:14]
评测

测评结果：100
用时：13ms
内存：18924kb

查看

[2022-03-30 02:43:50]
提交

answer


#include <bits/stdc++.h>
#define N 202200
using namespace std;
int sze, las, lnk[N << 1], len[N << 1], nxt[N << 1][10];
 
void extend(int c) {
    int cur = ++sze, p; cur[len] = las[len] + 1;
    for (p = las; p && !nxt[p][c]; p = lnk[p])
        nxt[p][c] = cur;
    if (!p) lnk[cur] = 1;
    else {
        int q = nxt[p][c];
        if (len[q] == len[p] + 1) lnk[cur] = q;
        else {
            int cln = ++sze; cln[len] = p[len] + 1;
            memcpy(nxt[cln], nxt[q], sizeof nxt[q]);
            lnk[cln] = lnk[q], lnk[q] = lnk[cur] = cln;
            for (; p && nxt[p][c] == q; p = lnk[p])
                nxt[p][c] = cln;
        }
    } las = cur;
}
 
int n, a, b, c[12], d[N];
long long f[N];
char s[N];
 
inline int go(int p, int ch, int le) {
    while (p != 1 && !nxt[p][ch])
        p = lnk[p], le = len[p];
    if (nxt[p][ch]) p = nxt[p][ch], ++le;
    return le;
}
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 0; i <= 9; ++i)
        scanf("%d", c + i);
    cin >> a >> b;
 
    las = sze = 1;
    int p = 1, t = 0, le = 0;
    for (int i = 1, j = 1; i <= n; ++i) {
        extend(s[i] - '0');
        while (t < n && go(p, s[t + 1] - '0', le) >= t + 1 - i) {
            int ch = s[++t] - '0';
            while (p != 1 && !nxt[p][ch])
                le = len[p = lnk[p]];
            if (nxt[p][ch]) p = nxt[p][ch], ++le;
        }
        while (j <= t) d[j++] = i + 1;
    }
 
    static int q[N], ql = 1, qr = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + c[s[i] - '0'];
        while (ql <= qr && q[ql] < d[i] - 1) ++ql;
        if (ql <= qr) {
            int j = q[ql];
            f[i] = min(f[i], f[j] + 1ll * a * (i - j) + b);
        }
        while (ql <= qr && (f[i] - 1ll * a * i) <= (f[q[qr]] - 1ll * a * q[qr])) --qr;
        q[++qr] = i;
    }
 
    cout << f[n] << endl;
 
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 2ms

memory: 9776kb

input:

75902254188305020153265646636543016308121578993465
861 520 899 835 182 401 640 780 136 282
50 500

output:

result:

ok answer is '20968'

Test #2:

score: 10

Accepted

time: 4ms

memory: 9860kb

input:

0604099983365439103293148513340002146605464429999987780100621387726951980692690201398795518328124417
258 958 925 647 415 662 591 225 294 761
1 1

output:

result:

ok answer is '5889'

Test #3:

score: 10

Accepted

time: 0ms

memory: 11980kb

input:

08218913670165447723153562370549386381711380431842858277022719973080819387485328444919681527790176060627303826546247484140477434828672640479794131501115583983463596800484713238900414170161023324262261
679 478 803 834 961 954 269 432 740 101
1 2000

output:

result:

ok answer is '126123'

Test #4:

score: 10

Accepted

time: 4ms

memory: 9844kb

input:

105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...

output:

result:

ok answer is '1258663'

Test #5:

score: 10

Accepted

time: 0ms

memory: 12084kb

input:

010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...

output:

result:

ok answer is '634386'

Test #6:

score: 10

Accepted

time: 4ms

memory: 14524kb

input:

101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...

output:

result:

ok answer is '3608448'

Test #7:

score: 10

Accepted

time: 4ms

memory: 18740kb

input:

259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...

output:

46857468

result:

ok answer is '46857468'

Test #8:

score: 10

Accepted

time: 12ms

memory: 18856kb

input:

228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...

output:

38860522

result:

ok answer is '38860522'

Test #9:

score: 10

Accepted

time: 13ms

memory: 18924kb

input:

559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...

output:

34081603

result:

ok answer is '34081603'

Test #10:

score: 10

Accepted

time: 13ms

memory: 18708kb

input:

010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...

output:

result:

ok answer is '3071979'