# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
206771 | 2020-03-05T08:16:56 Z | rzbt | Zapina (COCI20_zapina) | C++14 | 85 ms | 2808 KB |
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 355 typedef long long ll; using namespace std; ll n; const ll MOD =1e9+7; ll dp[355][355][2]; ll koeficijent[MAXN][MAXN]; int main() { for(ll i=0;i<MAXN;i++){ koeficijent[i][0]=1; } for(ll i=1;i<MAXN;i++){ for(ll j=1;j<MAXN;j++){ koeficijent[i][j]=koeficijent[i-1][j]+koeficijent[i-1][j-1]; } } scanf("%d", &n); dp[1][0][0]=1; dp[1][1][1]=1; for(ll i=2;i<=n;i++){ dp[1][i][0]=1; } for(ll i=2;i<=n;i++){ for(ll j=0;j<=n;j++){ for(ll k=0;k<=j;k++){ if(k==i){ //printf(" %d %d %d %d %d\n",i,j,k,dp[i-1][j-k][1],dp[i-1][j-k][0]); dp[i][j][1]=(dp[i][j][1]+koeficijent[j][k]*dp[i-1][j-k][1])%MOD; dp[i][j][1]=(dp[i][j][1]+koeficijent[j][k]*dp[i-1][j-k][0])%MOD; }else{ //printf(" %d %d %d %d\n",i,j,k,dp[i-1][j-k][1]); dp[i][j][1]=(dp[i][j][1]+koeficijent[j][k]*dp[i-1][j-k][1])%MOD; dp[i][j][0]=(dp[i][j][0]+koeficijent[j][k]*dp[i-1][j-k][0])%MOD; } } } } printf("%d",dp[n][n][1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1272 KB | Output is correct |
2 | Correct | 5 ms | 1272 KB | Output is correct |
3 | Correct | 6 ms | 1276 KB | Output is correct |
4 | Correct | 5 ms | 1272 KB | Output is correct |
5 | Correct | 5 ms | 1400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1272 KB | Output is correct |
2 | Correct | 5 ms | 1272 KB | Output is correct |
3 | Correct | 6 ms | 1276 KB | Output is correct |
4 | Correct | 5 ms | 1272 KB | Output is correct |
5 | Correct | 5 ms | 1400 KB | Output is correct |
6 | Correct | 5 ms | 1272 KB | Output is correct |
7 | Correct | 6 ms | 1400 KB | Output is correct |
8 | Correct | 5 ms | 1272 KB | Output is correct |
9 | Correct | 6 ms | 1404 KB | Output is correct |
10 | Correct | 5 ms | 1400 KB | Output is correct |
11 | Correct | 6 ms | 1400 KB | Output is correct |
12 | Correct | 5 ms | 1400 KB | Output is correct |
13 | Correct | 5 ms | 1400 KB | Output is correct |
14 | Correct | 6 ms | 1400 KB | Output is correct |
15 | Correct | 5 ms | 1400 KB | Output is correct |
16 | Correct | 5 ms | 1400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1272 KB | Output is correct |
2 | Correct | 5 ms | 1272 KB | Output is correct |
3 | Correct | 6 ms | 1276 KB | Output is correct |
4 | Correct | 5 ms | 1272 KB | Output is correct |
5 | Correct | 5 ms | 1400 KB | Output is correct |
6 | Correct | 5 ms | 1272 KB | Output is correct |
7 | Correct | 6 ms | 1400 KB | Output is correct |
8 | Correct | 5 ms | 1272 KB | Output is correct |
9 | Correct | 6 ms | 1404 KB | Output is correct |
10 | Correct | 5 ms | 1400 KB | Output is correct |
11 | Correct | 6 ms | 1400 KB | Output is correct |
12 | Correct | 5 ms | 1400 KB | Output is correct |
13 | Correct | 5 ms | 1400 KB | Output is correct |
14 | Correct | 6 ms | 1400 KB | Output is correct |
15 | Correct | 5 ms | 1400 KB | Output is correct |
16 | Correct | 5 ms | 1400 KB | Output is correct |
17 | Incorrect | 85 ms | 2808 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |