QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414496 | #3107. Debugging | shepherd | AC ✓ | 26ms | 11008kb | C++20 | 1.5kb | 2024-05-19 04:33:15 | 2024-05-19 04:33:16 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LLOCAL
#include "./debug.h"
#else
#define var(...)
#define debugArr(...)
#endif
using namespace std;
#define len(a) static_cast<int>((a).size())
#define present(c, x) (c.find(x) != c.end())
#define printDecimal(d) std::cout << std::setprecision(d) << std::fixed
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr const int iinf = 1e9 + 7;
constexpr const ll inf = 1e18;
static constexpr const ll mod = 1000000007;
template <typename Fun>
class y_combinator_result {
Fun fun_;
public:
template <typename T>
explicit y_combinator_result(T&& fun) : fun_{std::forward<T>(fun)} {}
template <typename... ArgTs>
decltype(auto) operator()(ArgTs&&... args) {
return fun_(std::ref(*this), std::forward<ArgTs>(args)...);
}
};
template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
int main() {
std::ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
ll r, p;
cin >> n >> r >> p;
vector<ll> dp(n + 1, inf);
dp[1] = dp[0] = 0;
auto solve = y_combinator([&](auto self, int x) {
if (dp[x] != inf) return dp[x];
for (int i = 2; i <= x; i++) {
dp[x] = min(dp[x], self((x + i - 1) / i) + r + p * (i - 1));
}
return dp[x];
});
cout << solve(n) << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
input:
339 7 1
output:
39
result:
ok single line: '39'
Test #2:
score: 0
Accepted
time: 26ms
memory: 11008kb
input:
1000000 1000000000 1000000000
output:
38000000000
result:
ok single line: '38000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
1 1 1000000000
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
1 1000000000 1
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1 1000000000 1000000000
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 26ms
memory: 10920kb
input:
1000000 1 1
output:
38
result:
ok single line: '38'
Test #8:
score: 0
Accepted
time: 22ms
memory: 10996kb
input:
1000000 1 1000000000
output:
20000000020
result:
ok single line: '20000000020'
Test #9:
score: 0
Accepted
time: 23ms
memory: 10924kb
input:
1000000 1000000000 1
output:
1000999999
result:
ok single line: '1000999999'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
2 200 300
output:
500
result:
ok single line: '500'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 1000000000 300
output:
1000000300
result:
ok single line: '1000000300'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
2 3 1000000000
output:
1000000003
result:
ok single line: '1000000003'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 1 1
output:
7
result:
ok single line: '7'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
12 1 1
output:
7
result:
ok single line: '7'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
13 1 1
output:
8
result:
ok single line: '8'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
9 1 1
output:
6
result:
ok single line: '6'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
9 1 2
output:
10
result:
ok single line: '10'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
9 11 10
output:
62
result:
ok single line: '62'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
9 41 10
output:
121
result:
ok single line: '121'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
9 39 10
output:
118
result:
ok single line: '118'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
973 1001 999
output:
19990
result:
ok single line: '19990'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
972 1001 999
output:
18993
result:
ok single line: '18993'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
3073 2001 999
output:
29985
result:
ok single line: '29985'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
29918 400000000 3
output:
400089751
result:
ok single line: '400089751'
Test #25:
score: 0
Accepted
time: 5ms
memory: 4320kb
input:
177147 1 1
output:
33
result:
ok single line: '33'
Test #26:
score: 0
Accepted
time: 5ms
memory: 4404kb
input:
177148 1 1
output:
34
result:
ok single line: '34'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3984kb
input:
82944 2 1
output:
41
result:
ok single line: '41'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
82945 2 1
output:
42
result:
ok single line: '42'
Test #29:
score: 0
Accepted
time: 5ms
memory: 4588kb
input:
200705 1000001 99999
output:
10099965
result:
ok single line: '10099965'
Test #30:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
79508 200 3
output:
981
result:
ok single line: '981'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
79507 200 3
output:
978
result:
ok single line: '978'
Test #32:
score: 0
Accepted
time: 11ms
memory: 6448kb
input:
439401 200 3
output:
1100
result:
ok single line: '1100'
Test #33:
score: 0
Accepted
time: 11ms
memory: 6508kb
input:
439400 200 3
output:
1097
result:
ok single line: '1097'
Test #34:
score: 0
Accepted
time: 5ms
memory: 4600kb
input:
194482 200 3
output:
1043
result:
ok single line: '1043'
Test #35:
score: 0
Accepted
time: 5ms
memory: 4604kb
input:
194481 200 3
output:
1040
result:
ok single line: '1040'
Test #36:
score: 0
Accepted
time: 13ms
memory: 7172kb
input:
511759 200 3
output:
1112
result:
ok single line: '1112'
Test #37:
score: 0
Accepted
time: 13ms
memory: 7176kb
input:
511758 200 3
output:
1109
result:
ok single line: '1109'
Test #38:
score: 0
Accepted
time: 2ms
memory: 3824kb
input:
78733 999999999 666666666
output:
24333333309
result:
ok single line: '24333333309'
Test #39:
score: 0
Accepted
time: 3ms
memory: 3928kb
input:
78732 999999999 666666666
output:
23999999976
result:
ok single line: '23999999976'
Test #40:
score: 0
Accepted
time: 6ms
memory: 4944kb
input:
233281 999999999 222666222
output:
14679986652
result:
ok single line: '14679986652'
Test #41:
score: 0
Accepted
time: 6ms
memory: 4932kb
input:
233280 999999999 222666222
output:
14570651541
result:
ok single line: '14570651541'
Test #42:
score: 0
Accepted
time: 3ms
memory: 4232kb
input:
117650 73 11
output:
845
result:
ok single line: '845'
Test #43:
score: 0
Accepted
time: 3ms
memory: 4052kb
input:
117649 73 11
output:
834
result:
ok single line: '834'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1025 1 10
output:
119
result:
ok single line: '119'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1024 1 10
output:
110
result:
ok single line: '110'
Test #46:
score: 0
Accepted
time: 19ms
memory: 10280kb
input:
900000 300 5
output:
1800
result:
ok single line: '1800'
Test #47:
score: 0
Accepted
time: 24ms
memory: 10420kb
input:
955553 400 7
output:
2454
result:
ok single line: '2454'
Test #48:
score: 0
Accepted
time: 19ms
memory: 10076kb
input:
888888 500000 3
output:
1005652
result:
ok single line: '1005652'
Test #49:
score: 0
Accepted
time: 22ms
memory: 10960kb
input:
999999 500000 133
output:
1265734
result:
ok single line: '1265734'
Test #50:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
2916 200 3
output:
718
result:
ok single line: '718'
Test #51:
score: 0
Accepted
time: 23ms
memory: 10716kb
input:
996004 315573 31
output:
692960
result:
ok single line: '692960'
Test #52:
score: 0
Accepted
time: 26ms
memory: 11000kb
input:
1000000 150000 7
output:
313986
result:
ok single line: '313986'
Test #53:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
603 61 13
output:
452
result:
ok single line: '452'
Test #54:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
382 80 45
output:
940
result:
ok single line: '940'
Test #55:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
348 14 22
output:
310
result:
ok single line: '310'
Test #56:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
7572 35102 4503
output:
288085
result:
ok single line: '288085'
Test #57:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
74769 82337 2160
output:
465428
result:
ok single line: '465428'
Test #58:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
3771 69223 5382
output:
427588
result:
ok single line: '427588'
Test #59:
score: 0
Accepted
time: 7ms
memory: 5208kb
input:
268437 539077352 29419680
output:
4342888840
result:
ok single line: '4342888840'
Test #60:
score: 0
Accepted
time: 7ms
memory: 6364kb
input:
416400 337281008 66559517
output:
4890228702
result:
ok single line: '4890228702'
Test #61:
score: 0
Accepted
time: 25ms
memory: 10920kb
input:
980056 688822864 19932229
output:
4919099266
result:
ok single line: '4919099266'
Test #62:
score: 0
Accepted
time: 14ms
memory: 8492kb
input:
683873 788575673 85007858
output:
9005351889
result:
ok single line: '9005351889'
Test #63:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1 100 20
output:
0
result:
ok single line: '0'
Test #64:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 10 1
output:
19
result:
ok single line: '19'
Test #65:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
16 1 10
output:
44
result:
ok single line: '44'