結果
問題 | 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;}