oj.uz

Submission #1059042

# Submission time Handle Problem Language Result Execution time Memory
1059042 2024-08-14T16:24:48 Z RiverFlow Magneti (COCI21_magneti) C++14
110 / 110
 20 ms 14552 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}
const int N = (int)52;
const int L = (int)1e4 + 7;

int Pow(int a, long long b) {
    int res = 1;
    for(; b > 0; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) res = 1ll * res * a % mod;
    return res;
}

int P[L], F[L];

int add(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int C(int k, int n) {
    return mul(P[n], mul(F[k], F[n - k]));
}
int distribute(int k, int n) {
    return C(n - 1, n + k - 1);
}
void prepare() {
    const int n = L - 3;
    P[0] = 1;
    FOR(i, 1, n) P[i] = mul(P[i - 1], i);
    F[n] = Pow(P[n], mod - 2);
    FOD(i, n - 1, 0) F[i] = mul(F[i + 1], i + 1);
};

int r[N];

void Add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}

int dp[N][N][L];

void main_code() {
    int n, l;
    cin >> n >> l;
    FOR(i, 1, n) cin >> r[i];
    sort(r + 1, r + n + 1);

    FOR(i, 0, n - 1) r[i] = r[i + 1];

    dp[1][1][1] = 1;
    for(int i = 1; i < n; ++i)
    for(int j = 1; j <= i; ++j)
    FOR(k, 1, l) if (dp[i][j][k] > 0) {
        // new_set
        Add(dp[i + 1][j + 1][k + 1], mul(j + 1, dp[i][j][k]));
        // extend
        if (k + r[i] <= l)
            Add(dp[i + 1][j][k + r[i]], mul(2 * j, dp[i][j][k]));
        // merge
        if (k + 2 * r[i] - 1 <= l and j > 1)
            Add(dp[i + 1][j - 1][k + 2 * r[i] - 1], mul(j - 1, dp[i][j][k]));
    }
    int ans = 0;
    FOR(d, 1, l) {
        // dp[n][1][d]
        int f = dp[n][1][d];
        f = mul(f, distribute(l - d, n + 1));
        Add(ans, f);
    }
    cout << ans;

}


/*     Let the river flows naturally     */

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7680 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 5 ms 4188 KB Output is correct
7 Correct 6 ms 3164 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 1 ms 3416 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7680 KB Output is correct
2 Correct 2 ms 5468 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 5 ms 4188 KB Output is correct
7 Correct 6 ms 3164 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2908 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 2 ms 2908 KB Output is correct
14 Correct 1 ms 2904 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Correct 1 ms 2904 KB Output is correct
17 Correct 1 ms 3160 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 2 ms 4444 KB Output is correct
22 Correct 1 ms 3416 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 3420 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 3420 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 1 ms 2908 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 20 ms 13244 KB Output is correct
32 Correct 13 ms 10800 KB Output is correct
33 Correct 20 ms 13404 KB Output is correct
34 Correct 5 ms 4956 KB Output is correct
35 Correct 19 ms 13148 KB Output is correct
36 Correct 1 ms 3164 KB Output is correct
37 Correct 20 ms 13804 KB Output is correct
38 Correct 5 ms 8284 KB Output is correct
39 Correct 19 ms 14552 KB Output is correct
40 Correct 5 ms 5208 KB Output is correct
41 Correct 20 ms 13268 KB Output is correct
42 Correct 1 ms 2652 KB Output is correct
43 Correct 14 ms 9688 KB Output is correct
44 Correct 2 ms 3932 KB Output is correct
45 Correct 13 ms 10124 KB Output is correct
46 Correct 1 ms 2396 KB Output is correct
47 Correct 4 ms 4696 KB Output is correct
48 Correct 3 ms 4444 KB Output is correct
49 Correct 1 ms 2652 KB Output is correct
50 Correct 1 ms 2652 KB Output is correct