QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601691 | #562. 码农 | Made_in_Code | 100 ✓ | 3ms | 14288kb | C++14 | 1.5kb | 2024-09-30 10:54:31 | 2024-09-30 10:54:31 |
Judging History
answer
#include <iostream>
using namespace std;
const int kMaxN = 1e5 + 1, kInf = 1e9;
struct V {
int f, l, p, e[10];
} v[kMaxN << 1];
int n, k, b, h, t, w[10], f[kMaxN];
string s;
pair<int, int> q[kMaxN];
void Insert(int i, int x) {
static int m = 1, r = 1;
int p = r;
v[++m].l = v[p].l + 1, v[m].p = i;
for (; p && !v[p].e[x]; p = v[p].f) {
v[p].e[x] = m;
}
if (p) {
int q = v[p].e[x];
if (v[p].l + 1 == v[q].l) {
v[m].f = q, r = m;
} else {
v[++m] = v[q], v[m].l = v[p].l + 1;
for (; p && v[p].e[x] == q; p = v[p].f) {
v[p].e[x] = m;
}
v[m - 1].f = v[q].f = m, r = m - 1;
}
} else {
v[m].f = 1, r = m;
}
}
void Push(int w, int i) {
for (; t >= h && q[t].first >= w; t--) {
}
q[++t] = {w, i};
}
int Pop(int i) {
for (; h <= t && q[h].second < i; h++) {
}
return h <= t ? q[h].first : kInf;
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
cin >> s;
for (int i = 0; i < 10; i++) {
cin >> w[i];
}
cin >> k >> b;
n = s.size(), h = 1, v[1].p = -1;
for (int i = 0, y = 1; i < n; i++) {
int x = s[i] - '0';
Insert(i, x), f[i] = f[i - 1 + !i] + w[x], y = v[y].e[x];
for (; y && v[y].p + v[v[y].f].l >= i; y = v[y].f) {
}
if (y) {
f[i] = min(f[i], Pop(max(v[y].p, i - v[y].l)) + k * i);
}
Push(f[i] - k * i + b, i);
}
cout << f[n - 1] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 3616kb
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: 1ms
memory: 5620kb
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: 3624kb
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: 5592kb
input:
105317817326678173266278173266781861452966757817326678173266278886145296675781732667817326646678173266274192117326678173266784326678173266466781732662741921173271467739032664667817326627419211244018646678173266274192667817326627419211732667817326678432667817326646676064694317326627419211732667817326...
output:
1258663
result:
ok answer is '1258663'
Test #5:
score: 10
Accepted
time: 1ms
memory: 7852kb
input:
010101010101310101000101010101010101010101015194010101410101310101010101016101050901010101010101010101010101010121010101010301010101010101050101010131010401019101030101010101010106010101010101010301113101010101060101010101010221310101010101010101010201010101010101010101010101010201010101010101010301...
output:
634386
result:
ok answer is '634386'
Test #6:
score: 10
Accepted
time: 2ms
memory: 9816kb
input:
101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011010110101101101011011010110101101101011010110110101101101011010110110101101101011010110110101101011011010110110101101011011010110101101101011011...
output:
3608448
result:
ok answer is '3608448'
Test #7:
score: 10
Accepted
time: 0ms
memory: 13380kb
input:
259056990780332590569987271259056990780332590569949056998727125905699078033259056998286994905632095600332590569982253590569907803325905699872712590569907803325905699490569987271259056990780332590569982869949056320956003325905699822589490569987271259056990780332590569982869949056320956003325905699822...
output:
46857468
result:
ok answer is '46857468'
Test #8:
score: 10
Accepted
time: 0ms
memory: 14288kb
input:
228255514297409372831124051231457518830714580983978118191715409980887870392763255958771396014724099273225818044544335318830714580983978118191715409980887870392763255958771396014724099273222875394216198066164777774453584645720613199953220643394961533112597700983978118191715409980887870392763255958771...
output:
38860522
result:
ok answer is '38860522'
Test #9:
score: 10
Accepted
time: 0ms
memory: 14200kb
input:
559026120443215529932053298946836947788255576080102636079256978346848066124067848713074979476892430650387372942634392777955392777605987788887027251714708216083863607925697834949925247190947471443668150708082380654358861507758294311830016300385819376425818027205596619887481716476691219729850438192848...
output:
34081603
result:
ok answer is '34081603'
Test #10:
score: 10
Accepted
time: 3ms
memory: 14164kb
input:
010101010101010101010101010101010101000101010101010101010101010101010101010101010103010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101015101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010601010101010101...
output:
3071979
result:
ok answer is '3071979'