oj.uz

Submission #512733

# Submission time Handle Problem Language Result Execution time Memory
512733 2022-01-16T17:18:41 Z blue Anagramistica (COCI21_anagramistica) C++17
110 / 110
 15 ms 16712 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

const ll mod = 1'000'000'007;

int ad(ll a, ll b)
{
    return (a+b)%mod;
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    string s[n];
    vi val{0};
    for(int i = 0; i < n; i++)
    {
        cin >> s[i];
        sort(s[i].begin(), s[i].end());
    }
    sort(s, s+n);


    for(int i = 0; i < n; i++)
    {
        if(i == 0 || s[i] != s[i-1]) val.push_back(1);
        else val.back()++;
    }



    int ch[1+n][1+n];
    for(int i = 0; i <= n; i++)
    {
        ch[i][0] = ch[i][i] = 1;
        for(int j = 1; j < i; j++)
            ch[i][j] = (ch[i-1][j] + ch[i-1][j-1]) % mod;
    }

    int z = int(val.size())-1;

    vvi dp(1+z, vi(1+k, 0));
    dp[0][0] = 1;

    for(int i = 1; i <= z; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            for(int c = 0; j - (c*(c-1)/2) >= 0 && c <= val[i]; c++)
            {
                dp[i][j] = ad(dp[i][j], mul(ch[val[i]][c], dp[i-1][j - (c*(c-1))/2]));
            }
        }
    }

    cout << dp[z][k] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 260 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Correct 9 ms 9164 KB Output is correct
3 Correct 10 ms 12364 KB Output is correct
4 Correct 13 ms 15948 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 260 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 5 ms 6476 KB Output is correct
7 Correct 9 ms 9164 KB Output is correct
8 Correct 10 ms 12364 KB Output is correct
9 Correct 13 ms 15948 KB Output is correct
10 Correct 3 ms 1868 KB Output is correct
11 Correct 2 ms 1740 KB Output is correct
12 Correct 3 ms 4300 KB Output is correct
13 Correct 4 ms 4300 KB Output is correct
14 Correct 7 ms 9288 KB Output is correct
15 Correct 7 ms 9216 KB Output is correct
16 Correct 15 ms 16712 KB Output is correct
17 Correct 15 ms 16144 KB Output is correct
18 Correct 11 ms 16080 KB Output is correct