結果
問題 | No.2610 Decreasing LCMs |
ユーザー | FplusFplusF |
提出日時 | 2024-01-19 23:07:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 407 ms / 1,000 ms |
コード長 | 2,018 bytes |
コンパイル時間 | 3,619 ms |
コンパイル使用メモリ | 266,132 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-28 05:02:02 |
合計ジャッジ時間 | 10,915 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using pll=pair<ll,ll>; using tll=tuple<ll,ll,ll>; using ld=long double; const ll INF=(1ll<<60); #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define all(v) v.begin(),v.end() template<class T> void chmin(T &a,T b){ if(a>b){ a=b; } } template<class T> void chmax(T &a,T b){ if(a<b){ a=b; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); auto f=[&](ll a,ll b){ ll ret=1; rep(i,b) ret*=a; return ret; }; vector<ll> v; ll mx=1e8; rep(i,30){ if(mx<f(2,i)) break; rep(j,30){ if(mx<f(3,j)) break; rep(k,20){ if(mx<f(5,k)) break; ll x=f(2,i),y=f(3,j),z=f(5,k); vector<__int128> now={x,y,z,(__int128)x*y,(__int128)y*z,(__int128)x*z,(__int128)x*y*z}; for(auto l:now){ if(mx<l) continue; v.push_back((ll)l); } } } } sort(all(v)); v.erase(unique(all(v)),v.end()); ll sz=(ll)v.size(); ll n; cin >> n; vector<vector<ll>> dp(n,vector<ll>(sz,0)); vector<vector<pll>> pre(n,vector<pll>(sz)); rep(i,sz) dp[0][i]=INF; rep(i,n-1){ rep(j,sz){ if(dp[i][j]==0) continue; for(ll k=j+1;k<sz;k++){ if(lcm(v[j],v[k])<dp[i][j]){ if(dp[i+1][k]<lcm(v[j],v[k])){ dp[i+1][k]=lcm(v[j],v[k]); pre[i+1][k]={i,j}; } } } } } ll ni=-1,nj=-1; rep(i,sz){ if(dp[n-1][i]!=0){ ni=n-1; nj=i; break; } } if(ni==-1) assert(0); vector<ll> ans={v[nj]}; while(ni!=0){ tie(ni,nj)=pre[ni][nj]; ans.push_back(v[nj]); } reverse(all(ans)); rep(i,n){ cout << ans[i] << ' '; } cout << '\n'; }