結果
問題 |
No.1862 Copy and Paste
|
ユーザー |
|
提出日時 | 2022-03-15 19:26:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,207 ms / 2,000 ms |
コード長 | 984 bytes |
コンパイル時間 | 1,375 ms |
コンパイル使用メモリ | 132,212 KB |
最終ジャッジ日時 | 2025-01-28 09:47:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <iostream> #include <unordered_map> #include <unordered_set> #include <set> #include <vector> #include <numeric> #include <algorithm> #include <queue> #include <string> #include <random> #include <array> #include <climits> #include <map> #include <cassert> #include <stack> #include <iomanip> #include <cfloat> #include <bitset> #include <fstream> #include <chrono> long long int a, b; std::unordered_map<int, long> cache; long long int solve(const int n) { if (n == 1) return 0; if (cache.find(n) != cache.end()) return cache[n]; long long int min = (n - 1) * b + a; for (auto i = 2; i * i <= n; ++i) { const auto j = (n + i - 1) / i; const auto r = solve(j) + b * (i - 1) + a; const auto r2 = solve(i) + b * (j - 1) + a; min = std::min({ min, r, r2 }); } return cache[n] = min; } int main() { int n; std::cin >> a >> b >> n; const auto result = solve(n); std::cout << result << '\n'; //std::cerr << cache.size() << '\n'; //std::cerr << count << '\n'; }