首页 > 代码库 > BZOJ 4868 [Shoi2017]期末考试 ——三分 枚举
BZOJ 4868 [Shoi2017]期末考试 ——三分 枚举
考场上xjb三分过掉了。
然后$sdfzyhx$、$silvernebula$ $O(n)$虐掉了。
我还是太菜了
#include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define ll long long #define inf 10000000LL #define llinf 10000000000000000LL #define maxn 100005 void Finout() { freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); } int n,m,t[maxn],b[maxn]; ll A,B,C; namespace Subtask1{ ll cal(int mid) { ll ret=0,cnt0=0,cnt1=0; F(i,1,n) ret+=max((mid-t[i])*C,0LL); F(i,1,m) { if (b[i]<=mid) cnt0+=mid-b[i]; else cnt1+=b[i]-mid; } if (A>=B) ret+=cnt1*B; else { if (cnt0>=cnt1) ret+=cnt1*A; else ret+=cnt0*A+(cnt1-cnt0)*B; } return ret; } void solve() { int l=0,r=0; F(i,1,m) r=max(r,b[i]); while (r-l>=4) { int m1=(l+r)/2,m2=(l+r)/2+1; if (cal(m1)>cal(m2)) l=m1; else r=m2; } ll ans=llinf; F(i,l,r) ans=min(ans,cal(i)); printf("%lld\n",ans); } } namespace Subtask2{ void solve() { ll ret=0,cnt0=0,cnt1=0,mini=llinf; F(i,1,n) mini=min(mini,1LL*t[i]); F(i,1,m) { if (b[i]<=mini) cnt0+=mini-b[i]; else cnt1+=b[i]-mini; } if (A>=B) ret+=cnt1*B; else { if (cnt0>=cnt1) ret+=cnt1*A; else ret+=cnt0*A+(cnt1-cnt0)*B; } printf("%lld\n",ret); } } int main() { scanf("%lld%lld%lld",&A,&B,&C); scanf("%d%d",&n,&m); F(i,1,n) scanf("%d",&t[i]); F(i,1,m) scanf("%d",&b[i]); if (C>=inf) Subtask2::solve(); else Subtask1::solve(); fclose(stdin); fclose(stdout); }
BZOJ 4868 [Shoi2017]期末考试 ——三分 枚举
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。