QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22370 | #2356. Partition of Queries | geiwmhdcds# | WA | 3ms | 3736kb | C++20 | 777b | 2022-03-09 16:31:50 | 2022-04-30 00:58:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int S[1000005],T[1000005];
long long f[1000005];
int q[1000005];
double slope(int x,int y){
return 1.0*(f[y]+1ll*S[y]*T[y]-f[x]-1ll*S[x]*T[x])/(T[y]-T[x]);
}
int main(){
int n,y;
cin>>n>>y;
scanf("%s",s+1);
for(int i=1;i<=n;++i){
S[i]=S[i-1]+(s[i]=='?');
T[i]=T[i-1]+(s[i]=='+');
}
int head=0,tail=-1;
q[++tail]=0;
for(int i=1;i<=n;++i){
while(head<tail&&slope(q[head],q[head+1])<S[i])++head;
int zy=q[head];
f[i]=f[zy]+1ll*(S[i]-S[zy])*T[zy]-y;
f[i]=max(f[i],0ll);
while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i))--tail;
q[++tail]=i;
}
long long ans=0;
for(int i=1;i<=n;++i){
if(s[i]=='?')ans+=T[i-1];
}
cout<<ans-f[n]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3736kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 3ms
memory: 3532kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3636kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3600kb
input:
10 0 ++?+??++??
output:
8
result:
wrong answer 1st lines differ - expected: '0', found: '8'