QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#137287#2356. Partition of Queriessalvator_noster#WA 2ms10004kbC++142.0kb2023-08-10 09:35:242023-08-10 09:35:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 09:35:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:10004kb
  • [2023-08-10 09:35:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int SIZE = 1000000 + 5;

int getInt(void) {
	int ch = getchar(), res = 0;
	while (!isdigit(ch)) {
		ch = getchar();
	}
	for (; isdigit(ch); ch = getchar()) {
		res = res * 10 + (ch - '0');
	}
	return res;
}

int n, y;
char str[SIZE];
int li[SIZE], cnt;
ll sum1[SIZE], sum2[SIZE];
ll dp[SIZE];

ll ki[SIZE], bi[SIZE];
int scnt;

void ins(ll k, ll b) {
	if (!scnt) {
		++scnt;
		ki[scnt] = k, bi[scnt] = b;
		return;
	}
	if (k == ki[scnt]) {
		if (bi[scnt] > b) {
			bi[scnt] = b;
		}
		return;
	}
	while (scnt >= 2 &&
			(__int128)(bi[scnt - 1] - bi[scnt]) * (k - ki[scnt])
			< (__int128)(b - bi[scnt]) * (ki[scnt - 1] - ki[scnt])) {
		--scnt;
	}
	++scnt;
	ki[scnt] = k, bi[scnt] = b;
	return;
}

ll qry(ll x) {
	if (scnt == 1) {
		return ki[1] * x + bi[1];
	}
	int le = 1, ri = scnt - 1;
	ll ans = 1e18;
	while (le <= ri) {
		int mid = (le + ri) >> 1;
		ll tmp1 = ki[mid] * x + bi[mid];
		ll tmp2 = ki[mid + 1] * x + bi[mid + 1];
		ans = min(ans, min(tmp1, tmp2));
		if (tmp1 >= tmp2) {
			ri = mid - 1;
		} else {
			le = mid + 1;
		}
	}
	return ans;
}

int main(void) {
	scanf("%d%d%s", &n, &y, str + 1);
	int cntP = 0;
	for (int i = 1; i <= n; ++i) {
		if (str[i] == '+') {
			++cntP;
		} else {
			++cnt;
			li[cnt] = cntP;
			cntP = 0;
		}
	}
	// for (int i = 1; i <= cnt; ++i) {
	// 	printf("li[%d] = %d\n", i, li[i]);
	// }
	for (int i = 1; i <= cnt; ++i) {
		sum1[i] = sum1[i - 1] + li[i];
		sum2[i] = sum2[i - 1] + (ll)i * li[i];
	}
	ins(0, 0);
	dp[1] = y;
	ins(sum1[1], dp[1] + sum2[1]);
	for (int i = 2; i <= cnt; ++i) {
		dp[i] = sum1[i - 1] * i - sum2[i - 1] + y + qry(-i);
		// printf("dp[%d] = %lld\n", i, dp[i]);
		ins(sum1[i], dp[i] + sum2[i]);
	}
	ll ans = 0;
	for (int i = 1; i <= cnt; ++i) {
		ans += (ll)li[i] * (cnt - i + 1);
	}
	for (int i = 1; i <= cnt; ++i) {
		ans = min(ans, dp[i] + (sum1[cnt] - sum1[i]) * (cnt + 1) - (sum2[cnt] - sum2[i]));
	}
	printf("%lld\n", ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 10004kb

input:

6 5
++??+?

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7708kb

input:

6 8
++??+?

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 2ms
memory: 9812kb

input:

5 1
+++++

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 7960kb

input:

10 0
++?+??++??

output:

2

result:

wrong answer 1st lines differ - expected: '0', found: '2'