QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414496#3107. DebuggingshepherdAC ✓26ms11008kbC++201.5kb2024-05-19 04:33:152024-05-19 04:33:16

Judging History

This is the latest submission verdict.

  • [2024-05-19 04:33:16]
  • Judged
  • Verdict: AC
  • Time: 26ms
  • Memory: 11008kb
  • [2024-05-19 04:33:15]
  • Submitted

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';
}

詳細信息

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'