QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#8719 | #562. 码农 | LCGUO | 100 ✓ | 12ms | 24416kb | C++20 | 2.6kb | 2021-04-03 20:50:26 | 2021-12-19 10:52:58 |
Judging History
answer
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005, C = 10;
int n;
char s[N];
struct State;
const int INF = 1000000005;
State* top, *last[N];
struct State {
int len, minPos;
State *fa, *go[C];
State(int len = 0) : len(len), fa(NULL) {
memset(go, 0, sizeof(go));
minPos = INF;
}
State* extend(State *start, int ch) {
State *p = this;
State *np = new(top++) State(len + 1);
while (p && !p->go[ch]) {
p->go[ch] = np;
p = p->fa;
}
if (!p) {
np->fa = start;
} else {
State *q = p->go[ch];
if (p->len + 1 == q->len) {
np->fa = q;
} else {
State *nq = new(top++) State(p->len + 1);
memcpy(nq->go, q->go, sizeof(q->go));
nq->fa = q->fa;
np->fa = q->fa = nq;
while (p && p->go[ch] == q) {
p->go[ch] = nq;
p = p->fa;
}
}
}
return np;
}
};
State pool[N << 1];
int cost[C], a, b;
int nxt[N];
long long dp[N];
int main() {
scanf("%s", s);
n = strlen(s);
top = pool;
State *root = new(top++) State(0);
last[0] = root;
for (int i = 0; i < n; ++i) {
last[i + 1] = last[i]->extend(root, s[i] - '0');
}
for (int i = 0; i < n; ++i) {
for (State *p = last[i + 1]; p && p->minPos == INF; p = p->fa) {
p->minPos = i;
}
}
State *u = root;
int cur = 0, curLen = 0;
for (int i = 0; i < n; ++i) {
if (cur < i) {
u = root;
cur = i;
curLen = 0;
} else {
if (u != root) {
--curLen;
if (curLen == u->fa->len) {
u = u->fa;
}
}
}
while (cur + 1 < n && u->go[s[cur + 1] - '0']->minPos <= i) {
u = u->go[s[++cur] - '0'];
++curLen;
}
nxt[i] = cur;
}
for (int i = 0; i < 10; ++i) {
scanf("%d", cost + i);
}
scanf("%d%d", &a, &b);
dp[0] = cost[s[0] - '0'];
deque<pair<long long, long long> > q;
q.push_back(make_pair(nxt[0], dp[0] + b));
for (int i = 1; i < n; ++i) {
while (q.size() && q.front().first < i) {
q.pop_front();
}
dp[i] = dp[i - 1] + cost[s[i] - '0'];
if (q.size()) {
dp[i] = min(dp[i], q.front().second + (long long)a * i);
}
long long cost = dp[i] - (long long)a * i + b;
while (q.size() && q.back().second >= cost) {
q.pop_back();
}
q.push_back(make_pair(nxt[i], cost));
}
cout << dp[n - 1] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 22488kb
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: 2ms
memory: 22388kb
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: 3ms
memory: 22448kb
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: 22508kb
input:
10531781732667817326627817326678186145296675781732667817326627888614529667578173266781732664667817326627419211732667817326678432667817326646678173266274192117327146773903266466781732662741921124401864667817326627419266781732662741921173266781732667843266781732664667606469431732662741921173266781732667843266781732664832667817326646676064694317326691773566788173077326646676064694317326627419211732667812117328122678178667817326627419219467817326627419211732714677390326646676477390714677390326646678...
output:
1258663
result:
ok answer is '1258663'
Test #5:
score: 10
Accepted
time: 4ms
memory: 22760kb
input:
01010101010131010100010101010101010101010101519401010141010131010101010101610105090101010101010101010101010101012101010101030101010101010105010101013101040101910103010101010101010601010101010101030111310101010106010101010101022131010101010101010101020101010101010101010101010101020101010101010101030101010104010101010171010101020101010101010101010101010101070101010191010101090101710101310101010101010101010101010101010101010801010101014104010101010101010108010101010109010101020141010101010182010101...
output:
634386
result:
ok answer is '634386'
Test #6:
score: 10
Accepted
time: 9ms
memory: 24156kb
input:
10110101101101011010110110101101101011010110110101101011011010110110101101011011010110110101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110110101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110...
output:
3608448
result:
ok answer is '3608448'
Test #7:
score: 10
Accepted
time: 10ms
memory: 24376kb
input:
25905699078033259056998727125905699078033259056994905699872712590569907803325905699828699490563209560033259056998225359056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982258949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699859056990780336994905699872712590569907803325089056998727125905699078033259056998286994905632095600332590569982258949056998727125905699078006994905632095600332590569982253590569...
output:
46857468
result:
ok answer is '46857468'
Test #8:
score: 10
Accepted
time: 7ms
memory: 24368kb
input:
22825551429740937283112405123145751883071458098397811819171540998088787039276325595877139601472409927322581804454433531883071458098397811819171540998088787039276325595877139601472409927322287539421619806616477777445358464572061319995322064339496153311259770098397811819171540998088787039276325595877139601472409927322581804454433531883005469165399289745824096376876084472665250974109084264513163151933659625884425958771396014724099273222875394216198066164777774453584645720613199953220643394961533112...
output:
38860522
result:
ok answer is '38860522'
Test #9:
score: 10
Accepted
time: 12ms
memory: 24384kb
input:
55902612044321552993205329894683694778825557608010263607925697834684806612406784871307497947689243065038737294263439277795539277760598778888702725171470821608386360792569783494992524719094747144366815070808238065435886150775829431183001630038581937642581802720559661988748171647669121972985043819284802347689243065038737294263439277795539277760598778888702725171470821608386360792569783494992524719094747144366815070808238065435886150775829431183001630062329401166311147024976628317692665988991606179...
output:
34081603
result:
ok answer is '34081603'
Test #10:
score: 10
Accepted
time: 4ms
memory: 24416kb
input:
01010101010101010101010101010101010100010101010101010101010101010101010101010101010301010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101510101010101010101010101010101010101010101010101010101010101010101010101010101010101010101060101010101010101010101010101010101010101010101010101010101010101010100010101010101010101010101010101010121010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
3071979
result:
ok answer is '3071979'