結果
問題 | No.1738 What's in the box? |
ユーザー | karinohito |
提出日時 | 2021-12-30 17:06:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 839 bytes |
コンパイル時間 | 2,041 ms |
コンパイル使用メモリ | 169,988 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-06 11:21:15 |
合計ジャッジ時間 | 3,855 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
//TLE解法 #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(A) A.begin(),A.end() using vll = vector<ll>; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) ll gcd(ll(a), ll(b)) { ll c = a; while (a % b != 0) { c = a % b; a = b; b = c; } return b; } vll DP(300005,1e18); ll dfs(ll n){ if(n==1){ DP[1]=0; return 0; } ll res=1e18; if(DP[n]<1e17)return DP[n]; for(ll i=1;i*i<=n;i++){ //cout<<n<<endl; if(n%i==0){ if(DP[i]>1e17)dfs(i); res=min(res,DP[i]+n/i); if(i!=1)if(DP[n/i]>1e17)dfs(n/i); res=min(res,DP[n/i]+i); } } DP[n]=res; return res; } int main() { ll N,M; cin>>N>>M; ll S=0; vll W(N); rep(i,N){ cin>>W[i]; S+=W[i]; } if(S==0){ rep(i,N)cout<<(i==N-1?"0\n":"0 "); return 0; } rep(i,N)cout<<W[i]*M/(S)<<(i==N-1?"\n":" "); }