QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22388 | #2356. Partition of Queries | Qyc_AK_NOI2022# | WA | 1ms | 1820kb | C++11 | 1.6kb | 2022-03-09 17:00:24 | 2022-04-30 00:59:46 |
Judging History
answer
#include <cstdio>
using namespace std;
typedef long long ll;
inline int rd(){
int x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
int n,k,val[1000010];
char s[1000010];
ll dp[1000010],sum[1000010];
inline int mmax(int x,int y){return x>y?x:y;}
inline ll mmin(int x,int y){return x<y?x:y;}
inline ll price(int l,int r){
return sum[r]-sum[l-1]-(ll)(r-l+1)*val[r+1];
}
inline ll upd(int from,int to){
return dp[from-1]+k+price(from+1,to);
}
struct stk{
int sl[1000010],sr[1000010],p[1000010],at;
inline void init(){p[at=1]=1,sl[1]=1,sr[1]=n;}
inline void push(const int x){
int lx=0;
while(at && sr[at]>x){
int u=p[at];
if(upd(x,sr[at])>=upd(u,sr[at]))break;
int l=mmax(sl[at],x+1),r=sr[at],mid;
if(upd(x,l)<upd(u,l)){
lx=l,--at;
continue;
}
while(l<r){
mid=l+r+1>>1;
if(upd(u,mid)>upd(x,mid))
l=mid;
else r=mid-1;
}
lx=l;
break;
}
if(lx)p[++at]=x,sl[at]=lx,sr[at]=n;
}
inline void proc(const int x){
int l=1,r=at,mid;
while(l<r){
mid=l+r>>1;
if(sr[mid]<x)l=mid+1;
else r=mid;
}
dp[x]=mmin(upd(p[l],x),price(1,x));
}
}ss;
int main(){
n=rd(),k=rd();
scanf("%s",s+1);
int at=0;
for(int i=1;i<=n;++i)
if(s[i]=='+')++at;
else ++val[at];
n=at;
dp[1]=val[1];
for(int i=n-1;i;--i)
val[i]+=val[i+1];
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+val[i];
ss.init();
for(int i=2;i<=n;++i)
ss.proc(i),ss.push(i);
printf("%lld\n",mmin(dp[n],dp[n-1]+k));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 1772kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 1812kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 1784kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 1820kb
input:
10 0 ++?+??++??
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'