QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456366 | #8772. House Deconstruction | NKheyuxiang | TL | 0ms | 0kb | C++14 | 1.3kb | 2024-06-27 20:15:06 | 2024-06-27 20:15:08 |
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