結果

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

ソースコード

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;


	 REP(i,N){
		 if(x[i]<S){
			 qL.push(i);
		 }
		 else{
			 qR.push(i);
		 }
	 }



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

	 while(1){

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

		 ll s=u*(p-x[l])+(u-w[l])*(x[r]-x[l]);   // left
		 ll t=u*(x[r]-p)+(u-w[r])*(x[r]-x[l]);   // right


		 if(s<t){

			 qL.pop();

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

			 p=x[l];

		 }
		 else{

			 qR.pop();

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

			 p=x[r];



		 }




		 if(qL.empty() || qR.empty()) break;

	 }



	 if(qL.empty()){

		 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