QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#867077 | #6460. Mountain Scenes | ammarm | AC ✓ | 362ms | 11264kb | C++17 | 997b | 2025-01-23 02:37:40 | 2025-01-23 02:37:48 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'