結果
問題 | No.376 立方体のN等分 (2) |
ユーザー |
![]() |
提出日時 | 2016-06-07 16:49:47 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1,673 ms / 5,000 ms |
コード長 | 1,943 bytes |
コンパイル時間 | 1,828 ms |
コンパイル使用メモリ | 112,324 KB |
実行使用メモリ | 291,740 KB |
最終ジャッジ日時 | 2024-11-06 23:28:14 |
合計ジャッジ時間 | 15,101 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include<iostream> #include<cmath> #include<algorithm> #include<map> #include<set> #include<vector> using namespace std; #define MAX 10000001 long long N; vector<long long> insuu; long long insuun=0; long long pc=0; long long ansmin; long long cou=0; map<long long,map<long long,map<long long,set<long long>>>> memo; void search2(long long a,long long b,long long c,int sn,int pl){ if(a+b+c>=ansmin){ if(memo.find(a)!=memo.end()&&memo[a].find(b)!=memo[a].end()&&memo[a][b].find(c)!=memo[a][b].end()&&memo[a][b][c].find(sn)!=memo[a][b][c].end()){ memo[a][b][c].erase(sn); if(memo[a][b][c].empty()) memo[a][b].erase(c); if(memo[a][b].empty()) memo[a].erase(b); if(memo[a].empty()) memo.erase(a); } return; } if(memo.find(a)!=memo.end()&&memo[a].find(b)!=memo[a].end()&&memo[a][b].find(c)!=memo[a][b].end()&&memo[a][b][c].find(sn)!=memo[a][b][c].end()){ return; } else{ memo[a][b][c].insert(sn); memo[a][c][b].insert(sn); memo[b][a][c].insert(sn); memo[b][c][a].insert(sn); memo[c][b][a].insert(sn); memo[c][a][b].insert(sn); } if(sn==-1||sn==insuun){ ansmin=min(ansmin,a+b+c); return; } search2(a*insuu[sn],b,c,sn+pl,pl); search2(a,b*insuu[sn],c,sn+pl,pl); search2(a,b,c*insuu[sn],sn+pl,pl); } int main(){ vector<bool> arr; vector<long long> pn; cin>>N; long long ansmax=N-1; for(long long i=0;i<=MAX;i++){ arr.push_back(true); } arr[0]=false; arr[1]=false; for(long long i=2;i<=MAX;i++){ if(arr[i]){ pn.push_back(i); pc++; for(long long j=i*2;j<=MAX;j+=i){ arr[j]=false; } } } while(!arr.empty()) arr.pop_back(); for(long long i=0;i<pc;i++){ while(N%pn[i]==0){ N/=pn[i]; insuu.push_back(pn[i]); insuun++; } if(N==1) break; } while(!pn.empty()) pn.pop_back(); if(N!=1) insuu.push_back(N),insuun++; ansmin=ansmax+3; search2(1,1,1,insuun-1,-1); ansmin-=3; cout<<ansmin<<" "<<ansmax<<endl; }