QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456363#8772. House DeconstructionNKheyuxiangWA 137ms19684kbC++141.3kb2024-06-27 20:11:212024-06-27 20:11:21

Judging History

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

  • [2024-06-27 20:11:21]
  • 评测
  • 测评结果:WA
  • 用时:137ms
  • 内存:19684kb
  • [2024-06-27 20:11:21]
  • 提交

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;
		ad(ans.g,v.g);
	}
	printf("%lld\n%d",ans.f,ans.g);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 7892kb

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: 0
Accepted
time: 137ms
memory: 17448kb

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:

262753966206
1

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 128ms
memory: 18492kb

input:

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

output:

1212175277
8

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 94ms
memory: 17368kb

input:

1000000000 100000 200000
3068 H
3087 P
3106 H
33031 H
33037 P
33043 H
52370 H
52394 P
52418 H
62996 H
63067 P
63138 H
66040 H
66133 P
66226 H
71350 H
71351 P
71352 H
91852 H
91883 P
91914 H
105924 H
105969 H
105971 P
106018 H
106057 P
106145 H
116361 H
116385 P
116409 H
126036 H
126084 P
126132 H
12...

output:

4978306
463697368

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 108ms
memory: 18592kb

input:

1000000 150000 200000
2 H
3 H
6 H
8 H
16 P
17 H
19 P
20 P
21 P
24 H
28 H
33 H
37 P
38 H
40 H
44 P
48 H
49 P
58 P
59 P
60 H
62 P
65 P
70 H
72 H
76 P
77 H
79 P
84 P
93 H
96 P
101 H
104 H
106 P
110 H
111 P
112 H
116 H
124 P
125 H
126 H
127 H
128 P
134 H
135 P
137 P
138 P
140 H
142 H
145 H
146 H
147 H
1...

output:

1203722
86861366

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 132ms
memory: 19684kb

input:

1000000000 199999 200000
966788248 H
966788251 P
966788252 H
966788254 P
966788255 H
966788260 P
966788261 H
966788263 P
966788267 H
966788275 P
966788278 H
966788279 P
966788288 H
966788291 P
966788298 H
966788304 P
966788305 H
966788308 P
966788309 H
966788317 P
966788326 H
966788334 P
966788342 H...

output:

1098446
4586

result:

ok 2 lines

Test #8:

score: -100
Wrong Answer
time: 76ms
memory: 16960kb

input:

10000000 137967 139896
52 P
101 H
106 P
149 P
158 P
190 P
258 P
338 P
349 P
350 P
457 P
486 P
500 P
509 P
517 P
563 P
568 P
630 P
723 P
738 P
801 P
819 P
859 P
872 P
885 P
900 P
972 P
1004 P
1034 P
1087 P
1183 P
1236 P
1245 P
1268 P
1436 H
1481 P
1486 P
1511 P
1544 P
1607 P
1647 P
1685 P
1798 P
1819...

output:

636623653942
1

result:

wrong answer 1st lines differ - expected: '317845182248', found: '636623653942'