QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137287 | #2356. Partition of Queries | salvator_noster# | WA | 2ms | 10004kb | C++14 | 2.0kb | 2023-08-10 09:35:24 | 2023-08-10 09:35:25 |
Judging History
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'