結果
問題 |
No.555 世界史のレポート
|
ユーザー |
![]() |
提出日時 | 2017-09-08 11:29:26 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 238 ms / 2,000 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 1,332 ms |
コンパイル使用メモリ | 157,956 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 04:49:50 |
合計ジャッジ時間 | 3,819 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> #define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define REP1(i,n) for(ll i=1;i<=(n);i++) #define MOD 1000000007 #define int long long #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef vector<int> vec; typedef vector<vec> mat; const int INF = 1e9; int N; //N文字以上作る int C; //コピーコスト int V; //ペーストコスト int dp[101010]; //i文字ちょうど作る最小コスト signed main() { cin >> N; cin >> C >> V; dp[1] = 0; int ans = LLONG_MAX / 3; for (int i=2; i<=2*N-2; i++) { dp[i] = LLONG_MAX / 3; for (int j=1; j*j<=i; j++) { if (i % j == 0) { //jがiの約数 dp[i] = min(dp[i], dp[j] + C + V * (i / j - 1)); //i/jがiの約数 if (i / j != i) { dp[i] = min(dp[i], dp[i/j] + C + V * (j - 1)); } } } if (i >= N && ans > dp[i]) ans = dp[i]; } cout << ans << endl; }