結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー nebukuro09
提出日時 2019-08-30 22:28:52
言語 D
(dmd 2.111.0)
結果
TLE  
実行時間 -
コード長 1,094 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 655 ms
コンパイル使用メモリ 116,968 KB
実行使用メモリ 251,696 KB
最終ジャッジ日時 2024-06-22 02:26:19
合計ジャッジ時間 10,422 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 2 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio;

void main() {
    auto s = readln.split.map!(to!int);
    auto n = s[0];

    auto dp = new int[](n + 1);
    auto ans = new bool[][](n + 1);
    bool[] tmp;
    dp[] = 1 << 29;
    dp[0] = 0;

    foreach (i; 0..n) {
        for (int j = 1; i + j * j <= n; ++j) {
            if (dp[i] + j < dp[i + j * j]) {
                dp[i + j * j] = dp[i] + j;
                ans[i + j * j] = ans[i];
                bool last = i == 0 ? 0 : ans[i].back();
                foreach (_; 0..j) ans[i + j * j] ~= last, last ^= 1;
            }
            else if (dp[i] + j == dp[i + j * j]) {
                tmp = ans[i].dup;
                bool last = i == 0 ? 0 : ans[i].back();
                foreach (_; 0..j) tmp ~= last, last ^= 1;
                ans[i + j * j] = min(ans[i + j * j], tmp);
            }
        }
    }

    foreach (i; 0..ans[n].length) write(ans[n][i] ? 1 : 0);
    writeln;
}
0