CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-18 22:05:04 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.09 s1details
#2ACCEPTED0.08 s1details
#30.09 s1details
#40.07 s1details
#50.09 s1details
#6ACCEPTED0.07 s2details
#7ACCEPTED0.09 s2details
#80.08 s2details
#90.07 s2details
#100.09 s2details
#11ACCEPTED0.09 s3details
#12ACCEPTED0.09 s3details
#130.09 s3details
#140.08 s3details
#150.08 s3details

Code

#include <iostream>
#define F first
#define S second
using namespace std;
typedef long long ll;

ll dp[211][111][111];
const ll mod=1e9+7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    dp[0][0][0]=1;
    if (k>n) k=n;
    for (int i=0;i<2*n-1;i++){
        for (int ii=0;ii<=k;ii++){
            for (int iii=0;iii<=k;iii++){
                if (dp[i][ii][iii]&&ii+iii<=k){
                    ll tv=dp[i][ii][iii];
                    int t=1+i/2;
                    dp[i+1][ii][iii]+=tv;
                    dp[i+1][ii][iii]%=mod;
                    if (t%2==1){
                        if (t-ii>0){
                            dp[i+1][ii+1][iii]+=tv*(ll)(t-ii);
                            dp[i+1][ii+1][iii]%=mod;
                        }
                    }
                    else{
                        if (t-iii>0){
                            dp[i+1][ii][iii+1]+=tv*(ll)(t-iii);
                            dp[i+1][ii][iii+1]%=mod;
                        }
                    }
                }
            }
        }
    }
    ll v=0;
    for (int i=0;i<=k;i++){
        for (int ii=0;ii<=k;ii++){
            if (i+ii==k){
                v+=dp[2*n-1][i][ii];
                v%=mod;
            }
        }
    }
    cout<<v<<endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 2

correct output
240

user output
240

Test 2

Group: 1

Verdict: ACCEPTED

input
5 4

correct output
2728

user output
2728

Test 3

Group: 1

Verdict:

input
5 6

correct output
1960

user output
3368

Test 4

Group: 1

Verdict:

input
5 8

correct output
32

user output
3368

Test 5

Group: 1

Verdict:

input
5 10

correct output
0

user output
3368

Test 6

Group: 2

Verdict: ACCEPTED

input
10 4

correct output
1809464

user output
1809464

Test 7

Group: 2

Verdict: ACCEPTED

input
10 8

correct output
209594075

user output
209594075

Test 8

Group: 2

Verdict:

input
10 12

correct output
811277399

user output
915225111

Test 9

Group: 2

Verdict:

input
10 16

correct output
17275136

user output
915225111

Test 10

Group: 2

Verdict:

input
10 20

correct output
0

user output
915225111

Test 11

Group: 3

Verdict: ACCEPTED

input
100 40

correct output
126883191

user output
126883191

Test 12

Group: 3

Verdict: ACCEPTED

input
100 80

correct output
785497039

user output
785497039

Test 13

Group: 3

Verdict:

input
100 120

correct output
324216296

user output
408854794

Test 14

Group: 3

Verdict:

input
100 160

correct output
895190039

user output
408854794

Test 15

Group: 3

Verdict:

input
100 200

correct output
0

user output
408854794