oj.uz

Submission #397610

# Submission time Handle Problem Language Result Execution time Memory
397610 2021-05-02T14:20:50 Z MrRobot_28 Anagramistica (COCI21_anagramistica) C++17
40 / 110
 25 ms 34884 KB 
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define sz(a) (int)a.size()
const int mod = 1e9 + 7;
const int N = 2e3 + 100;
int cnk[N][N];
signed main()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cnk[i][j] = 0;
        }
    }
    cnk[0][0] = 1;
    for(int i = 1; i < N; i++)
    {
        cnk[i][0] = 1;
        for(int j = 1; j < N; j++)
        {
            cnk[i][j] = cnk[i - 1][j] + cnk[i - 1][j - 1];
        }
    }
    int n, k;
    cin >> n >> k;
    map<vector <int>, int> mp;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        vector <int> cnt(26, 0);
        for(int j = 0; j < sz(s); j++)
        {
            cnt[s[j] - 'a']++;
        }
        mp[cnt]++;
    }
    vector <int> dp(k + 1, 0);
    dp[0] = 1;
    for(auto p : mp)
    {
        int t = p.Y;
        for(int j = k; j >= 0; j--)
        {
            for(int f = t; f >= 1; f--)
            {
                int add = f * (f - 1) / 2;
             //   cout << dp[j] << " " << add << " " << cnk[t][f] << "\n";
                if(add + j <= k)
                {
                    dp[add + j] = (dp[add + j] + dp[j] * cnk[t][f]) % mod;
                }
            }
        }
     //   cout << dp[k] << "\n";
    }
    cout << dp[k];
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 34880 KB Output is correct
2 Correct 24 ms 34720 KB Output is correct
3 Correct 24 ms 34764 KB Output is correct
4 Correct 23 ms 34764 KB Output is correct
5 Correct 24 ms 34844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 34764 KB Output is correct
2 Correct 24 ms 34884 KB Output is correct
3 Correct 24 ms 34848 KB Output is correct
4 Correct 24 ms 34884 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 34880 KB Output is correct
2 Correct 24 ms 34720 KB Output is correct
3 Correct 24 ms 34764 KB Output is correct
4 Correct 23 ms 34764 KB Output is correct
5 Correct 24 ms 34844 KB Output is correct
6 Correct 24 ms 34764 KB Output is correct
7 Correct 24 ms 34884 KB Output is correct
8 Correct 24 ms 34848 KB Output is correct
9 Correct 24 ms 34884 KB Output is correct
10 Correct 24 ms 34828 KB Output is correct
11 Correct 24 ms 34760 KB Output is correct
12 Correct 25 ms 34884 KB Output is correct
13 Incorrect 25 ms 34768 KB Output isn't correct
14 Halted 0 ms 0 KB -