QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#637129 | #562. 码农 | hhoppitree | 100 ✓ | 102ms | 14556kb | C++17 | 2.2kb | 2024-10-13 09:53:40 | 2024-10-13 09:53:40 |
Judging History
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'