QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22370#2356. Partition of Queriesgeiwmhdcds#WA 3ms3736kbC++20777b2022-03-09 16:31:502022-04-30 00:58:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 00:58:09]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3736kb
  • [2022-03-09 16:31:50]
  • 提交

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'