結果

問題 No.3417 Tired Santa
コンテスト
ユーザー 👑 tails
提出日時 2025-12-24 05:49:09
言語 cLay
(20241019-1 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 831 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,036 ms
コンパイル使用メモリ 191,580 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-24 05:49:15
合計ジャッジ時間 4,095 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

int@n,@s,@x[n],@w[n],b[n+1];
b[0]=0;
b[1..n]=b[0..]+w[0..];
int c=bsearch_min[int,c,0,n](x[c]>=s);
vector<ll>m(n),t(n);
if(c>0){
	m[c-1]=(s-x[c-1])*(ll)b[n];
}
if(c<n){
	m[c]=(x[c]-s)*(ll)b[n];
}
rep(i,1,n){
	if(c-i-1>=0){
		ll d=b[n]-b[c]+b[c-i];
		t[c-i-1]=m[c-i]+(x[c-i]-x[c-i-1])*d;
	}
	REP(j,max(0,c-i),min(c-1,n-i)){
		ll d=b[n]-b[j+i+1]+b[j+1];
		t[j]=min(m[j+1]+(x[j+1]-x[j])*d,m[j+i]+(x[j+i]-x[j])*d);
	}
	if(c>0&&c+i-1<n){
		ll d=b[n]-b[c+i]+b[c];
		t[c-1]=m[c+i-1]+(x[c+i-1]-x[c-1])*d;
	}
	if(c<n&&c-i>=0){
		ll d=b[n]-b[c]+b[c-i];
		t[c]=m[c-i]+(x[c]-x[c-i])*d;
	}
	REP(j,max(c+1,i),min(c+i,n)){
		ll d=b[n]-b[j]+b[j-i];
		t[j]=min(m[j-i]+(x[j]-x[j-i])*d,m[j-1]+(x[j]-x[j-1])*d);
	}
	if(c+i<n){
		ll d=b[n]-b[c+i]+b[c];
		t[c+i]=m[c+i-1]+(x[c+i]-x[c+i-1])*d;
	}
	swap(m,t);
}
wt(c==0?m[n-1]:c==n?m[0]:min(m[0],m[n-1]));
0