結果

問題 No.3417 Tired Santa
コンテスト
ユーザー daiota
提出日時 2025-12-24 19:40:24
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,970 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,163 ms
コンパイル使用メモリ 203,696 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-24 19:40:27
合計ジャッジ時間 3,033 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)















int main(){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;




	ll N,S;
	cin >> N >> S;


	ll W=0;
	vector<ll> x(N),w(N);
	REP(i,N) cin >> x[i];
	REP(i,N){
		cin >> w[i];
		W+=w[i];
	}




	ll ans=0;
	ll u=W;
	if(S<x[0]){

		REP(i,N){
			if(i==0){
				ans+=u*(x[0]-S);
				u-=w[i];
			}
			else{
				ans+=u*(x[i]-x[i-1]);
				u-=w[i];
			}
		}

		cout << ans << endl;

		return 0;

	}


	ans=0;
	u=W;
	if(S>x[N-1]){

		for(i=N-1;i>=0;i--){
			if(i==N-1){
				ans+=u*(S-x[i]);
				u-=w[i];
			}
			else{
				ans+=u*(x[i+1]-x[i]);
				u-=w[i];
			}
		}

		cout << ans << endl;

		return 0;

	}

	vector<ll> c=w;
	for(i=1;i<N;i++) c[i]+=c[i-1];




	 priority_queue<ll> qL;
	 priority_queue<ll,vector<ll>,greater<ll> > qR;


	 ll M0=0,M1=0;
	 REP(i,N){
		 if(x[i]<S){
			 qL.push(i);
			 M0+=w[i]*(S-x[i]);
		 }
		 else{
			 qR.push(i);
			 M1+=w[i]*(x[i]-S);
		 }
	 }



	 ans=0;
	 u=W;
	 ll p=S;

	 while(1){

		 ll l=qL.top(),r=qR.top();

		 ll d=p-x[l];    // left
		 ll v0,v1;
		 v0=M0-w[l]*d;
		 if(l!=0) v0-=c[l-1]*d;
		 if(r!=0) v1=M1+(c[N-1]-c[r-1])*d;
		 else v1=M1+c[N-1]*d;


		 d=x[r]-p;       // right
		 ll u0,u1;
		 u1=M1-w[r]*d;
		 u1-=(c[N-1]-c[r])*d;
		 u0=M0+c[l]*d;




		 if(v0+v1<u0+u1){

			 qL.pop();

			 M1=v1;
			 M0=v0;


			 d=p-x[l];
			 ans+=u*d;
			 u-=w[l];

			 p=x[l];


		 }

		 else{

			 qR.pop();

			 M1=u1;
			 M0=u0;

			 d=x[r]-p;
			 ans+=u*d;
			 u-=w[r];

			 p=x[r];

		 }

		 if(M0==0 || M1==0) break;

	 }



	 if(M0==0){

		 while(!qR.empty()){

			 ll r=qR.top();
			 qR.pop();

			 ll d=x[r]-p;
			 ans+=u*d;
			 u-=w[r];

			 p=x[r];
		 }

		 cout << ans << endl;

	 }
	 else{

		 while(!qL.empty()){

			 ll l=qL.top();
			 qL.pop();

			 ll d=p-x[l];
			 ans+=u*d;
			 u-=w[l];

			 p=x[l];
		 }

		 cout << ans << endl;

	 }











  return 0;

}
0