結果
問題 | No.376 立方体のN等分 (2) |
ユーザー |
|
提出日時 | 2019-04-14 19:54:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,327 ms / 5,000 ms |
コード長 | 1,236 bytes |
コンパイル時間 | 1,869 ms |
コンパイル使用メモリ | 176,696 KB |
実行使用メモリ | 261,888 KB |
最終ジャッジ日時 | 2024-09-19 09:06:26 |
合計ジャッジ時間 | 20,550 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second #define dbg(x) cout<<#x" = "<<((x))<<endl template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} using pl = pair<ll,ll>; const ll INF = LLONG_MAX/3; ll n; const int N = 66; vector<ll> pf; int P; map<pl,ll> dp[N]; ll dfs(int d, ll a, ll b){ pl k(a,b); if(dp[d].count(k)) return dp[d][k]; if(d == P){ ll c = n/a/b; // printf(" d %d, (%lld %lld %lld)\n",d,a,b,c); return a+b+c-3; } ll ret = dfs(d+1, a, b); ret = min(ret, dfs(d+1, a*pf[d], b)); ret = min(ret, dfs(d+1, a, b*pf[d])); return dp[d][k] = ret; } int main(){ cin >>n; // prime factor ll t = n; for(ll i=2; i*i<=n; ++i){ while(t%i == 0){ t /= i; pf.pb(i); } } if(t>1) pf.pb(t); P = pf.size(); cout << dfs(0,1,1) << " " << n-1 << "\n"; return 0; }