QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456366#8772. House DeconstructionNKheyuxiangTL 0ms0kbC++141.3kb2024-06-27 20:15:062024-06-27 20:15:08

Judging History

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

  • [2024-06-27 20:15:08]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-06-27 20:15:06]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 998244353
#define N 400005
using namespace std;
char s[N];
void ad(int &x,int y){x-=((x+=y)>=mod)?mod:0;}
int len,n,m,cnt[N],pre[N],lst[N*2];
long long sum[N];
struct node{long long f;int g;}ans,dp[N],inf;
void min(node &A,node B){
	if(B.f<A.f) A=B;
	else if(B.f==A.f) ad(A.g,B.g);
}
node calc(int k){
	int st=0,ed=n;
	while(st<=n&&cnt[st]!=k) st++;
	while(ed>=0&&cnt[ed]!=cnt[n]+k) ed--;
	if(ed<st) return inf;
	dp[st]=node{0ll,1};
	for(int i=st+1;i<=ed;i++){
		dp[i]=inf;
		if(s[i]=='H') min(dp[i],dp[i-1]);
		if(pre[i]>=st){
			node v=dp[pre[i]];v.f+=abs(sum[i]-sum[pre[i]]);
			min(dp[i],v);
		}
	}
	dp[ed].f+=abs(sum[n]-sum[ed]+sum[st]+1ll*k*len);
	return dp[ed];
}
int main(){
	inf.f=1e18;
	cin>>len>>n>>m;n+=m;
	for(int i=0;i<=n;i++) lst[i]=-1;lst[m]=0;
	int l=0,r=0;
	for(int i=1;i<=n;i++){
		int x,t;cin>>x>>s[i];
		t=(s[i]=='P')?-1:1;
		cnt[i]=cnt[i-1]+t;
		sum[i]=sum[i-1]+t*x;
		pre[i]=lst[cnt[i]+m];
		lst[cnt[i]+m]=i;
		l=min(l,pre[i]);
		r=max(r,pre[i]);
	}
	r=r-cnt[n]-1;
	while(l<=r){
		int mid=l+r>>1;
		if(calc(mid).f>calc(mid+1).f) l=mid+1;
		else r=mid-1;
	}
	ans=calc(l);
	for(int i=l+1;;i++){
		node v=calc(i);
		if(v.f<ans.f) break;
		min(ans,v);
	}
	printf("%lld\n%d",ans.f,ans.g);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

6 2 4
1 P
2 H
3 P
4 H
5 H
6 H

output:


result: