QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#867077#6460. Mountain ScenesammarmAC ✓362ms11264kbC++17997b2025-01-23 02:37:402025-01-23 02:37:48

Judging History

This is the latest submission verdict.

  • [2025-01-23 02:37:48]
  • Judged
  • Verdict: AC
  • Time: 362ms
  • Memory: 11264kb
  • [2025-01-23 02:37:40]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int main() {
    int n, w, h;
    cin >> n >> w >> h;

    long long mod = 1e9 + 7;

    vector<vector<long long>> dp(w + 1, vector<long long>(n + 1, -1));

    function<long long(int, int)> solve = [&](int idx, int rem) {
        if (idx == w) {
            return 1LL;
        }
        if (dp[idx][rem] != -1) {
            return dp[idx][rem];
        }

        long long ans = 0;
        for (int cur = 0; cur <= min(h, rem); ++cur) {
            ans = (ans + solve(idx + 1, rem - cur)) % mod;
        }

        return dp[idx][rem] = ans;
    };

    long long total_scenes = solve(0, n);

    long long plain_scenes = 0;
    for (int i = 0; i <= h; ++i) {
        if (1LL * i * w <= n) {
            plain_scenes++;
        }
    }

    long long mountain_scenes = (total_scenes - plain_scenes + mod) % mod;

    cout << mountain_scenes << endl;

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

25 5 5

output:

7770

result:

ok single line: '7770'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

15 5 5

output:

6050

result:

ok single line: '6050'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3328kb

input:

10 10 1

output:

1022

result:

ok single line: '1022'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4 2 2

output:

6

result:

ok single line: '6'

Test #5:

score: 0
Accepted
time: 362ms
memory: 11264kb

input:

10000 100 100

output:

502424636

result:

ok single line: '502424636'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

10000 1 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 11264kb

input:

10000 100 1

output:

976371283

result:

ok single line: '976371283'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

10000 1 100

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

1 100 100

output:

100

result:

ok single line: '100'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

0 100 100

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 22ms
memory: 3584kb

input:

1420 36 79

output:

649438197

result:

ok single line: '649438197'

Test #12:

score: 0
Accepted
time: 4ms
memory: 3840kb

input:

1451 17 76

output:

264834562

result:

ok single line: '264834562'

Test #13:

score: 0
Accepted
time: 22ms
memory: 3796kb

input:

1664 33 80

output:

903182149

result:

ok single line: '903182149'

Test #14:

score: 0
Accepted
time: 16ms
memory: 7552kb

input:

5915 93 24

output:

635984237

result:

ok single line: '635984237'

Test #15:

score: 0
Accepted
time: 227ms
memory: 9216kb

input:

8577 86 92

output:

369573031

result:

ok single line: '369573031'

Test #16:

score: 0
Accepted
time: 62ms
memory: 4224kb

input:

1595 66 96

output:

42134373

result:

ok single line: '42134373'

Test #17:

score: 0
Accepted
time: 2ms
memory: 6016kb

input:

3430 99 4

output:

629396289

result:

ok single line: '629396289'

Test #18:

score: 0
Accepted
time: 152ms
memory: 7808kb

input:

6109 92 71

output:

177326550

result:

ok single line: '177326550'

Test #19:

score: 0
Accepted
time: 113ms
memory: 9856kb

input:

8560 98 57

output:

196315713

result:

ok single line: '196315713'

Test #20:

score: 0
Accepted
time: 191ms
memory: 9856kb

input:

9723 85 85

output:

297305331

result:

ok single line: '297305331'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

6665 7 41

output:

539331596

result:

ok single line: '539331596'

Test #22:

score: 0
Accepted
time: 10ms
memory: 6272kb

input:

6511 58 28

output:

701126549

result:

ok single line: '701126549'

Test #23:

score: 0
Accepted
time: 70ms
memory: 5248kb

input:

2835 94 51

output:

838020060

result:

ok single line: '838020060'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

65 33 94

output:

109739472

result:

ok single line: '109739472'

Test #25:

score: 0
Accepted
time: 37ms
memory: 8832kb

input:

9505 72 44

output:

676217746

result:

ok single line: '676217746'

Test #26:

score: 0
Accepted
time: 8ms
memory: 5888kb

input:

6912 45 31

output:

588848907

result:

ok single line: '588848907'

Test #27:

score: 0
Accepted
time: 49ms
memory: 4096kb

input:

1574 65 80

output:

189483116

result:

ok single line: '189483116'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

418 14 61

output:

519877002

result:

ok single line: '519877002'

Test #29:

score: 0
Accepted
time: 96ms
memory: 7936kb

input:

6637 88 58

output:

956699055

result:

ok single line: '956699055'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

4339 19 14

output:

359541896

result:

ok single line: '359541896'