QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#637129#562. 码农hhoppitree100 ✓102ms14556kbC++172.2kb2024-10-13 09:53:402024-10-13 09:53:40

Judging History

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

  • [2024-10-13 09:53:40]
  • 评测
  • 测评结果:100
  • 用时:102ms
  • 内存:14556kb
  • [2024-10-13 09:53:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct Node {
    int len, link, nxt[10];
} p[N << 1];

char s[N];
int n, val[10], lst = 1, tot = 1;

void extend(int c) {
    int cur = ++tot, z = lst;
    p[cur].len = p[z].len + 1;
    while (z && !p[z].nxt[c]) p[z].nxt[c] = cur, z = p[z].link;
    if (!p[z].nxt[c]) p[cur].link = 1;
    else {
        int v = p[z].nxt[c];
        if (p[v].len + 1 == p[z].len) {
            p[cur].link = v;
        } else {
            int clo = ++tot;
            p[clo] = p[v];
            p[clo].len = p[z].len + 1;
            while (z && p[z].nxt[c] == v) {
                p[z].nxt[c] = clo;
                z = p[z].link;
            }
            p[cur].link = p[v].link = clo;
        }
    }
    lst = cur;
}

int calc(int now, int ch, int len) {
    while (now && !p[now].nxt[ch]) {
        now = p[now].link;
        len = p[now].len;
    }
    if (p[now].nxt[ch]) {
        now = p[now].nxt[ch];
        ++len;
    }
    return len;
}

int d[N], f[N], mn[N];

void modify(int x, int y) {
    for (; x; x -= x & -x) mn[x] = min(mn[x], y);
}

int query(int x) {
    int res = 1e9;
    for (; x <= n; x += x & -x) res = min(res, mn[x]);
    return res;
}

signed main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 0; i < 10; ++i) scanf("%d", &val[i]);
    int a, b; scanf("%d%d", &a, &b);
    for (int i = 1, j = 1, t = 0, now = 1, len = 0; i <= n; ++i) {
        extend(s[i] - '0');
        while (t < n && calc(now, s[t + 1] - '0', len) >= t - i + 1) {
            int ch = s[++t] - '0';
            while (now && !p[now].nxt[ch]) {
                now = p[now].link;
                len = p[now].len;
            }
            if (p[now].nxt[ch]) {
                now = p[now].nxt[ch];
                ++len;
            }
        }
        while (j <= t) d[j++] = i + 1;
    }
    for (int i = 1; i <= n; ++i) mn[i] = 1e9;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + val[s[i] - '0'];
        f[i] = min(f[i], query(d[i] - 1) + i * a + b);
        modify(i, f[i] - i * a);
    }
    printf("%d\n", f[n]);
    return 0;
}

详细


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3984kb

input:

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

output:

20968

result:

ok answer is '20968'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3916kb

input:

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

output:

5889

result:

ok answer is '5889'

Test #3:

score: 10
Accepted
time: 0ms
memory: 3864kb

input:

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

output:

126123

result:

ok answer is '126123'

Test #4:

score: 10
Accepted
time: 1ms
memory: 4292kb

input:

105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...

output:

1258663

result:

ok answer is '1258663'

Test #5:

score: 10
Accepted
time: 3ms
memory: 7968kb

input:

010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...

output:

634386

result:

ok answer is '634386'

Test #6:

score: 10
Accepted
time: 4ms
memory: 12816kb

input:

101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...

output:

3608448

result:

ok answer is '3608448'

Test #7:

score: 10
Accepted
time: 8ms
memory: 14552kb

input:

259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...

output:

46857468

result:

ok answer is '46857468'

Test #8:

score: 10
Accepted
time: 7ms
memory: 14552kb

input:

228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...

output:

38860522

result:

ok answer is '38860522'

Test #9:

score: 10
Accepted
time: 7ms
memory: 14548kb

input:

559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...

output:

34081603

result:

ok answer is '34081603'

Test #10:

score: 10
Accepted
time: 102ms
memory: 14556kb

input:

010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...

output:

3071979

result:

ok answer is '3071979'