oj.uz

Submission #206772

# Submission time Handle Problem Language Result Execution time Memory
206772 2020-03-05T08:18:07 Z rzbt Zapina (COCI20_zapina) C++14
55 / 110
 90 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("%lld", &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("%lld",dp[n][n][1]);
    return 0;
}

Compilation message

zapina.cpp: In function 'int main()':
zapina.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1400 KB Output is correct
3 Correct 6 ms 1400 KB Output is correct
4 Correct 6 ms 1272 KB Output is correct
5 Correct 5 ms 1272 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1400 KB Output is correct
3 Correct 6 ms 1400 KB Output is correct
4 Correct 6 ms 1272 KB Output is correct
5 Correct 5 ms 1272 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 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 5 ms 1400 KB Output is correct
11 Correct 5 ms 1400 KB Output is correct
12 Correct 5 ms 1400 KB Output is correct
13 Correct 6 ms 1400 KB Output is correct
14 Correct 5 ms 1400 KB Output is correct
15 Correct 5 ms 1400 KB Output is correct
16 Correct 5 ms 1400 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 5 ms 1400 KB Output is correct
3 Correct 6 ms 1400 KB Output is correct
4 Correct 6 ms 1272 KB Output is correct
5 Correct 5 ms 1272 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 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 5 ms 1400 KB Output is correct
11 Correct 5 ms 1400 KB Output is correct
12 Correct 5 ms 1400 KB Output is correct
13 Correct 6 ms 1400 KB Output is correct
14 Correct 5 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 90 ms 2808 KB Output isn't correct
18 Halted 0 ms 0 KB -