結果

問題 No.2656 XOR Slimes
ユーザー parukiparuki
提出日時 2024-03-02 22:23:12
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 391 ms / 2,000 ms
コード長 867 bytes
コンパイル時間 49 ms
コンパイル使用メモリ 6,820 KB
実行使用メモリ 45,420 KB
最終ジャッジ日時 2024-09-29 16:27:14
合計ジャッジ時間 17,106 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function Main(input) {
    const lines = input.split("\n");
    var n = parseInt(lines[0]);
    let xs = lines[1].split(" ").map(Number);
    let as = lines[2].split(" ").map(Number);
    let dp = Array(n+1);
    dp.fill(Infinity);
    dp[0] = 0;
    for(let i=0; i<n; ++i) {
        let sum = as[i];
        let xor = as[i];
        for(let j=i+1; ; ++j) {
            // [i, j)は一つも合体しない。
            dp[j] = Math.min(dp[j], dp[i] + sum);
            if(j==n) break;
            sum += as[j];
            xor ^= as[j];
            // iとjは合体する。このときiとj-1の間はすべて合体してよい。
            // なぜならa+b>=a xor bが成り立つから。
            dp[j+1] = Math.min(dp[j+1], dp[i] + xor + xs[j]-xs[i]);
        }
    }
    console.log(dp[n]);
}
0