oj.uz

Submission #597734

# Submission time Handle Problem Language Result Execution time Memory
597734 2022-07-16T18:27:11 Z Deepesson NoM (RMI21_nom) C++17
34 / 100
 3 ms 2204 KB 
#include <bits/stdc++.h>
#define MAX 305


using ll  = long long;
const ll MOD = 1e9+7;

ll binominal[MAX][MAX];
bool exbin[MAX][MAX];
ll dpbin(int a,int b){
    if(!b)return 1;
    if(!a)return 0;
    if(exbin[a][b])return binominal[a][b];
    exbin[a][b]=true;
    return binominal[a][b] = (dpbin(a-1,b)+dpbin(a-1,b-1))%MOD;
}

bool existe[MAX][MAX];
ll tab[MAX][MAX];
ll fat[MAX];
std::vector<int> tamanhos;
ll dp(int nunca_pegou,int pegou_uma_vez,int seq){
    if(seq==tamanhos.size()){
        //std::cout<<"Chegou! "<<nunca_pegou+pegou_uma_vez<<"\n";
        if(nunca_pegou+pegou_uma_vez==0)
            return 1;
        return 0;
    }
    if(existe[nunca_pegou][pegou_uma_vez])return tab[nunca_pegou][pegou_uma_vez];
    existe[nunca_pegou][pegou_uma_vez]=true;
   // std::cout<<nunca_pegou<<" "<<pegou_uma_vez<<" "<<seq<<"\n";
    int tem_q_pegar = tamanhos[seq];
    ll resposta=0;
    for(int i=0;i<=std::min(tem_q_pegar,pegou_uma_vez);++i){
        int necessita = tem_q_pegar-i;
        if(nunca_pegou<necessita)continue;
        ll chance1 = dpbin(nunca_pegou,necessita);
        ll chance2 = dpbin(pegou_uma_vez,i);
        ll total = (chance1*chance2)%MOD;
        ll res = dp(nunca_pegou-necessita,pegou_uma_vez-i+necessita,seq+1);
        ll totalres = (total*res)%MOD;
        ll fatty = fat[tem_q_pegar];
        ll truetotral = (fatty*totalres)%MOD;
        resposta=(resposta+truetotral)%MOD;
    }
    return tab[nunca_pegou][pegou_uma_vez]=resposta;
}

int main()
{
   // std::cout<<dpbin(10,6)<<"\n";
    int N,M;
    std::cin>>N>>M;
    fat[0]=1;
    for(int i=1;i!=MAX;++i)fat[i]=(fat[i-1]*i)%MOD;
    {
        int x = (2*N)/M;
        for(int i=0;i!=M;++i)tamanhos.push_back(x);
        for(int i=0;i!=((2*N)%M);++i)tamanhos[i]++;
        ll xa=0;
        for(int i=0;i!=M;++i){
            xa+=tamanhos[i];
            //std::cout<<tamanhos[i]<<" \n"[i==M-1];
        }
        assert(xa==(2*N));
    }
    ll bonus=1;
    for(int i=0;i!=N;++i)bonus=(bonus*2)%MOD;
    std::cout<<((dp(N,0,0)*bonus)%MOD)<<"\n";
}

Compilation message

Main.cpp: In function 'll dp(int, int, int)':
Main.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(seq==tamanhos.size()){
      |        ~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 828 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 828 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 1204 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 2 ms 1748 KB Output is correct
23 Correct 1 ms 1492 KB Output is correct
24 Correct 2 ms 1876 KB Output is correct
25 Correct 3 ms 1620 KB Output is correct
26 Correct 1 ms 1620 KB Output is correct
27 Correct 2 ms 1848 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 828 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 1204 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 2 ms 1748 KB Output is correct
23 Correct 1 ms 1492 KB Output is correct
24 Correct 2 ms 1876 KB Output is correct
25 Correct 3 ms 1620 KB Output is correct
26 Correct 1 ms 1620 KB Output is correct
27 Correct 2 ms 1848 KB Output is correct
28 Runtime error 2 ms 2204 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 828 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 1204 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 2 ms 1748 KB Output is correct
23 Correct 1 ms 1492 KB Output is correct
24 Correct 2 ms 1876 KB Output is correct
25 Correct 3 ms 1620 KB Output is correct
26 Correct 1 ms 1620 KB Output is correct
27 Correct 2 ms 1848 KB Output is correct
28 Runtime error 2 ms 2204 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -