QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#8719#562. 码农LCGUO100 ✓12ms24416kbC++202.6kb2021-04-03 20:50:262021-12-19 10:52:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 10:52:58]
  • 评测
  • 测评结果:100
  • 用时:12ms
  • 内存:24416kb
  • [2021-04-03 20:50:26]
  • 提交

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'