QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601691#562. 码农Made_in_Code100 ✓3ms14288kbC++141.5kb2024-09-30 10:54:312024-09-30 10:54:31

Judging History

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

  • [2024-09-30 10:54:31]
  • 评测
  • 测评结果:100
  • 用时:3ms
  • 内存:14288kb
  • [2024-09-30 10:54:31]
  • 提交

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'