QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #456367 | #8772. House Deconstruction | NKheyuxiang | WA | 145ms | 19684kb | C++14 | 1.3kb | 2024-06-27 20:15:29 | 2024-06-27 20:15:31 |
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]-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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7896kb
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: 9880kb
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: 145ms
memory: 18828kb
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: 124ms
memory: 18536kb
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: 90ms
memory: 19168kb
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: 111ms
memory: 18664kb
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: 83ms
memory: 18672kb
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'