QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#421859#6460. Mountain Scenesnitrousoxide#WA 8ms11976kbC++14993b2024-05-26 08:40:482024-05-26 08:40:48

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 08:40:48]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:11976kb
  • [2024-05-26 08:40:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int modi = 1'000'000'007;

int dp[112][10240], s[112][10240];

inline void inc(int & x, int v) {
    x += v;
    if (x >= modi) {
        x -= modi;
    }
}

int main() {
    int n, w, h;
    cin >> n >> w >> h;
    for (int i = 0; i <= n; i++) {
        dp[1][i] = min(h+1, i+1);
        if (i != 0) s[1][i] = s[1][i-1];
        inc(s[1][i], dp[1][i]);
    }
    for (int i = 2; i <= w; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            if (j <= h) {
                dp[i][j] = s[i-1][j];
            } else {
                dp[i][j] = s[i-1][j] - s[i-1][j-h-1];
                if (dp[i][j] < 0) dp[i][j] += modi;
            }
        }
        s[i][0] = dp[i][0];
        for (int j = 1; j <= n; j++) {
            s[i][j] = s[i][j-1];
            inc(s[i][j], dp[i][j]);
        }
    }
    cout << (dp[w][n] - (min(n/w, h+1) + 1) % modi + modi) % modi << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5720kb

input:

25 5 5

output:

7770

result:

ok single line: '7770'

Test #2:

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

input:

15 5 5

output:

6050

result:

ok single line: '6050'

Test #3:

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

input:

10 10 1

output:

1022

result:

ok single line: '1022'

Test #4:

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

input:

4 2 2

output:

6

result:

ok single line: '6'

Test #5:

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

input:

10000 100 100

output:

502424636

result:

ok single line: '502424636'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 5744kb

input:

10000 1 1

output:

1000000006

result:

wrong answer 1st lines differ - expected: '0', found: '1000000006'