結果

問題 No.3417 Tired Santa
コンテスト
ユーザー daiota
提出日時 2025-12-24 07:53:35
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,691 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,052 ms
コンパイル使用メモリ 204,036 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-24 07:53:39
合計ジャッジ時間 3,185 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;

	}



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


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



	 ans=0;
	 u=W;
	 ll p=S;
	 while(1){

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


		 if(WL*(2*x[r]-x[l]-p)<WR*(p-2*x[l]+x[r])){
			 qR.pop();


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

			 WR-=w[r];


			 p=x[r];
		 }
		 else{
			 qL.pop();


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

			 WL-=w[l];

			 p=x[l];

		 }

		 if(WL==0 || WR==0) break;


	 }


	 ll d;
	 if(WL==0){

		 while(WR!=0){

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


			 d=x[r]-p;

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

			 WR-=w[r];

			 p=x[r];

		 }

		 cout << ans << endl;

	 }

     else{


		 while(WL!=0){

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

			 d=p-x[l];

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

			 WL-=w[l];

			 p=x[l];

		 }

		 cout << ans << endl;




	}







  return 0;

}
0