結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2019-08-30 22:31:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 1,424 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 184,812 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-06-11 14:01:13 |
合計ジャッジ時間 | 4,866 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> dp(300001, 1e9); vector<vector<int>> prv(300001); string Ans = "2"; void dfs(int N, vector<int>& v, int last){ if(N == 0){ deque<int> use[2]; // for(int a : v) cerr << a << " "; // cerr << endl; for(int a : v) use[a%2].push_back(a); for(int k=0; k<2; k++) sort(use[k].begin(), use[k].end()); string ans; bool onetop = false; for(int i : use[1]) for(int j=0; j<i; j++) ans.push_back('0' + j%2); while(use[0].size()){ int num; if(!onetop){ num = use[0].back(); use[0].pop_back(); }else{ num = use[0].front(); use[0].pop_front(); } for(int j=0; j<num; j++) ans.push_back('0' + (j+onetop)%2); onetop = !onetop; } Ans = min(ans, Ans); }else{ for(int a : prv[N]) if(last <= a){ v.push_back(a); dfs(N-a*a, v, a); v.pop_back(); } } } int main(){ int N; cin >> N; dp[0] = 0; for(int i=0; i<N; i++) for(int j=1; i+j*j<=N; j++){ if(dp[i+j*j] > dp[i] + j){ dp[i+j*j] = dp[i] + j; prv[i+j*j] = {j}; }else if(dp[i+j*j] >= dp[i] + j){ prv[i+j*j].push_back(j); } } vector<int> v; dfs(N, v, 0); cout << Ans << endl; return 0; }