QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#456380#8772. House DeconstructionNKheyuxiangTL 1ms9924kbC++141.4kb2024-06-27 20:24:342024-06-27 20:24:34

Judging History

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

  • [2024-06-27 20:24:34]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9924kb
  • [2024-06-27 20:24:34]
  • 提交

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];
	while(l+1<r){
		int mid=l+r>>1;
		if(calc(mid).f<calc(mid+1).f) r=mid;
		else l=mid;
	}
	ans.f=min(calc(l).f,calc(r).f);
	for(int i=r;;i++){
		node v=calc(i);
		if(v.f>ans.f) break;
		min(ans,v);
	}
	for(int i=r-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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7940kb

input:

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

output:

2
3

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 9924kb

input:

1000000000 2 4
1 P
6 H
31415926 H
999999998 H
999999999 H
1000000000 P

output:

4
1

result:

ok 2 lines

Test #3:

score: -100
Time Limit Exceeded

input:

1000000000 199999 200000
3087 P
3282 H
6407 H
6748 P
9535 P
10098 H
16470 H
22311 H
31045 H
31968 H
32549 H
33037 P
36005 P
36308 H
40284 P
46224 H
52394 P
54922 H
55800 P
56582 H
57548 H
62155 P
63067 P
64237 H
66133 P
71351 P
75667 P
79089 P
79646 P
81144 H
91883 P
96680 H
102797 H
105388 H
105971...

output:


result: