結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2019-08-30 22:14:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,641 ms / 2,000 ms |
コード長 | 999 bytes |
コンパイル時間 | 1,676 ms |
コンパイル使用メモリ | 171,308 KB |
実行使用メモリ | 182,912 KB |
最終ジャッジ日時 | 2024-06-11 13:57:55 |
合計ジャッジ時間 | 13,673 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#include <vector>using namespace std;#define REP(i,n) for (int i=0;i<(n);i++)#define REP2(i,m,n) for (int i=m;i<(n);i++)typedef long long ll;int N;ll dp[303030];ll par[303030];ll par2[303030];string ans[303030];void solve() {cin >> N;REP(i, N+1) dp[i] = 1LL << 59;dp[0] = 0;REP(i, N) for (ll 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];int last = i == 0 ? 0 : ans[i].back() - '0';REP(_, j) ans[i + j * j] += to_string(last), last ^= 1;} else if (dp[i] + j == dp[i + j * j]) {string tmp = ans[i];int last = i == 0 ? 0 : ans[i].back() - '0';REP(_, j) tmp += to_string(last), last ^= 1;ans[i + j * j] = min(ans[i + j * j], tmp);}}cout << ans[N] << "\n";}int main() {cin.tie(0);ios::sync_with_stdio(false);solve();}