oj.uz

Submission #1101132

# Submission time Handle Problem Language Result Execution time Memory
1101132 2024-10-15T15:22:07 Z InvMOD Zapina (COCI20_zapina) C++14
110 / 110
 241 ms 2384 KB 
#include <bits/stdc++.h>
using namespace std;


#define fi first
#define se second
#define gcd __gcd
#define sz(v) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 1, n)
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T &a, T b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T &a, T b){if(a > b) return a = b, true; return false;}

const int N = 400;
const ll MOD = 1e9+7;
const ll INF = 1e18;


int n, dp[2][N][N], C[N][N];

int add(int a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
    return a;
}

int mul(int a, int b){
    return (ll) a * b % MOD;
}

int get(int check, int rem, int cur){
    if(cur == n+1){
        if(rem != 0) return 0;
        return check;
    }
    if(rem == 0) return check;
    if(dp[check][rem][cur] != -1) return dp[check][rem][cur];

    int res = 0;
    FOR(i, 0, rem){
        ///How many different way to choose i from rem
        res = add(res, mul(C[rem][i], get((check | (cur == i)), rem - i, cur+1)));
    }
    return dp[check][rem][cur] = res;
}

void solve()
{
    cin >> n;
    memset(dp, -1, sizeof(dp));
    C[0][0] = 1;
    REP(i, n){
        FOR(j, 0, i){
            C[i][j] = C[i-1][j];
            if(j) C[i][j] = add(C[i][j], C[i-1][j-1]);
        }
    }

    cout << get(0, n, 1) <<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message

zapina.cpp: In function 'int main()':
zapina.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
zapina.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 2 ms 1784 KB Output is correct
3 Correct 2 ms 1632 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 2 ms 1784 KB Output is correct
3 Correct 2 ms 1632 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 2 ms 1784 KB Output is correct
14 Correct 2 ms 1620 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 2 ms 1784 KB Output is correct
3 Correct 2 ms 1632 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 2 ms 1784 KB Output is correct
14 Correct 2 ms 1620 KB Output is correct
15 Correct 2 ms 1620 KB Output is correct
16 Correct 1 ms 1620 KB Output is correct
17 Correct 105 ms 2164 KB Output is correct
18 Correct 3 ms 1620 KB Output is correct
19 Correct 24 ms 1988 KB Output is correct
20 Correct 2 ms 1780 KB Output is correct
21 Correct 144 ms 2132 KB Output is correct
22 Correct 23 ms 2040 KB Output is correct
23 Correct 3 ms 1620 KB Output is correct
24 Correct 32 ms 1876 KB Output is correct
25 Correct 21 ms 1876 KB Output is correct
26 Correct 41 ms 1876 KB Output is correct
27 Correct 208 ms 2380 KB Output is correct
28 Correct 208 ms 2132 KB Output is correct
29 Correct 209 ms 2272 KB Output is correct
30 Correct 206 ms 2384 KB Output is correct
31 Correct 204 ms 2304 KB Output is correct
32 Correct 206 ms 2132 KB Output is correct
33 Correct 209 ms 2132 KB Output is correct
34 Correct 216 ms 2132 KB Output is correct
35 Correct 211 ms 2296 KB Output is correct
36 Correct 221 ms 2132 KB Output is correct
37 Correct 241 ms 2288 KB Output is correct