QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456380 | #8772. House Deconstruction | NKheyuxiang | TL | 1ms | 9924kb | C++14 | 1.4kb | 2024-06-27 20:24:34 | 2024-06-27 20:24:34 |
Judging History
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...