QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22420 | #2356. Partition of Queries | Qyc_AK_NOI2022# | TL | 2ms | 2008kb | C++11 | 1.6kb | 2022-03-09 17:44:55 | 2022-04-30 01:02:57 |
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,q[500010],d[500010];
char s[1000010];
ll dp[500010],sum[500010];
inline ll upd(int f,int t){
return dp[f]+sum[t]-sum[f]-(ll)(d[t]-d[f])*q[t]+k;
}
inline ll mmax(ll x,ll y){return x>y?x:y;}
inline ll mmin(ll x,ll y){return x<y?x:y;}
struct stk{
int sl[500010],sr[500010],p[500010],at;
inline void init(){at=1,sl[1]=1,sr[1]=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]=upd(p[l],x);
}
inline void push(const int x){
int lx=0;
while(sr[at]>x){
int u=p[at];
if(upd(x,sr[at])>=upd(u,sr[at]))break;
int l=mmax(x+1,sl[at]),r=sr[at],mid;
if(upd(x,l)>upd(u,l)){--at,lx=l;continue;}
while(l<r){
mid=l+r>>1;
if(upd(x,mid)<upd(u,mid))r=mid;
else l=mid+1;
}
lx=l;break;
}
if(lx)p[++at]=x,sl[at]=lx,sr[at]=n;
}
}ss;
int main(){
n=rd(),k=rd();
scanf("%s",s+1);
int at=0,pl=0;
for(int i=1;i<=n;++i){
if(s[i]=='+'){
if(!pl)++at,pl=1;
++d[at];
}
else{
if(pl)pl=0;
++q[at];
}
}
n=at-pl;
for(int i=n-1;i>=0;--i)q[i]+=q[i+1];
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+(ll)d[i]*q[i];
d[i]=d[i-1]+d[i];
}
for(int i=1;i<=n;++i){
dp[i]=0x3f3f3f3f3f3f3f3f;
for(int j=0;j<i;++j)
dp[i]=mmin(dp[i],upd(j,i));
}
ll ans=0x3f3f3f3f3f3f3f3f;
for(int i=0;i<=n;++i)
ans=mmin(ans,sum[n]-sum[i]+dp[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: 1824kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 1772kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 1ms
memory: 1776kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 1712kb
input:
10 0 ++?+??++??
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 1828kb
input:
12 100 +?+++??+??++
output:
19
result:
ok single line: '19'
Test #6:
score: 0
Accepted
time: 1ms
memory: 1772kb
input:
1 1 ?
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 1772kb
input:
9 7 ++++++++?
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 1ms
memory: 1824kb
input:
9 8 ++++++++?
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 0ms
memory: 1964kb
input:
10 15 ++++++++??
output:
15
result:
ok single line: '15'
Test #10:
score: 0
Accepted
time: 1ms
memory: 1824kb
input:
5 3 +?+?+
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 0ms
memory: 1772kb
input:
10 5 +?+?+??+??
output:
10
result:
ok single line: '10'
Test #12:
score: 0
Accepted
time: 1ms
memory: 1708kb
input:
10 7 +?+?+??+??
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 1ms
memory: 2008kb
input:
15 4 +?+?+??+??+??+?
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 1ms
memory: 1968kb
input:
15 6 +?+?+??+??+??+?
output:
18
result:
ok single line: '18'
Test #15:
score: 0
Accepted
time: 1ms
memory: 1772kb
input:
19 8 +?+?+??+??+??+?++??
output:
28
result:
ok single line: '28'
Test #16:
score: 0
Accepted
time: 1ms
memory: 1764kb
input:
20 9 +?+?+??+??+??+?++???
output:
30
result:
ok single line: '30'
Test #17:
score: 0
Accepted
time: 1ms
memory: 1772kb
input:
500 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++++...
output:
2710
result:
ok single line: '2710'
Test #18:
score: 0
Accepted
time: 2ms
memory: 1824kb
input:
10000 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++...
output:
56616
result:
ok single line: '56616'
Test #19:
score: -100
Time Limit Exceeded
input:
500000 3000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...