結果

問題 No.3417 Tired Santa
コンテスト
ユーザー applejam
提出日時 2025-12-24 11:14:47
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 101 ms / 2,000 ms
コード長 2,071 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,139 ms
コンパイル使用メモリ 335,684 KB
実行使用メモリ 58,496 KB
最終ジャッジ日時 2025-12-24 11:14:55
合計ジャッジ時間 8,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)

using p = pair<ll, ll>;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; ll s; cin >> n >> s;
    vll x(n+1, s), w(n+1, 0); 
    rep(i, n)cin >> x[i+1]; rep(i, n)cin >> w[i+1];
    vector<p> vp = {{s, 0}};
    rep(i, n)vp.push_back({x[i+1], i+1});
    sort(all(vp));
    
    int a = 0;
    while(vp[a].first < s)a++;
    vll sum(n+2, 0); rep(i, n+1)sum[i+1] = sum[i] + w[vp[i].second];

    vvvll dp(n+1, vvll(n+1, vll(2, 1e18)));
    dp[a][a][0] = dp[a][a][1] = 0;
    rep2(k, 1, n+1){
        rep(j, k+1){
            int l = a-j, r = a + k - j;
            if(l < 0 || r < 0 || r > n)continue;
            ll tmp1 = sum[n+1] - (sum[r] - sum[l]), tmp2 = sum[n+1] - (sum[r+1] - sum[l+1]);
            ll tmp3 = sum[n+1] - (sum[r+1] - sum[l]); 
            ll d1 = x[vp[l+1].second] - x[vp[l].second], d2 = x[vp[r].second] - x[vp[r-1].second];
            ll d3 = x[vp[r].second] - x[vp[l+1].second], d4 = x[vp[r-1].second] - x[vp[l].second];
            ll d5 = x[vp[r].second] - x[vp[l].second];
            dp[l][r][0] = min({dp[l+1][r][0]+d1*tmp2 , dp[l+1][r][1] + (d1+d3)*tmp2,
                dp[l][r-1][0] + (d4+d2)*tmp1 + d5*tmp3, dp[l][r-1][1] + d2*tmp1 + d5*tmp3});
            dp[l][r][1] = min({dp[l+1][r][0] +d1*tmp2 + d5*tmp3, dp[l+1][r][1] + (d1+d3)*tmp2 + d5*tmp3,
                dp[l][r-1][0] + (d2+d4)*tmp1, dp[l][r-1][1] + d2*tmp1});
            
        }
    }cout << min(dp[0][n][0], dp[0][n][1]) << endl;

    return 0;
}
0