oj.uz

Submission #421085

# Submission time Handle Problem Language Result Execution time Memory
421085 2021-06-08T17:26:08 Z Chaska Anagramistica (COCI21_anagramistica) C++11
110 / 110
 40 ms 39856 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+5,mod = 1e9+7;
typedef long long ll;
int n,k;
string a[N];
set<string> s;
map<string,int> sTOi;
ll cnt,res[N];
ll cb[N][N],dp[N][N];
int main()
{
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for (int i=0;i<n;i++) 
        cin >> a[i];

    for (int i=0;i<n;i++) 
        sort(a[i].begin(),a[i].end());

    for (int i=0;i<n;i++) s.insert(a[i]);

    for (string u : s) sTOi[u] = ++cnt;


    for (int i=0;i<n;i++) res[sTOi[a[i]]]++;
    

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

    dp[0][0] = 1;
    for (int i=1;i<=n;i++) for (int q=0;q<=k;q++) {
        for (int j=0;j<=res[i];j++) {
            ll x = j*(j-1);
            x/= 2;
            ll y;
            y = cb[res[i]][j];
            y %= mod;
           
            if (q>=x) {
                dp[i][q] = dp[i][q] + y*dp[i-1][q-x];
                dp[i][q] %= mod;
            }
        }
       
    }
    cout << dp[n][k];
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16572 KB Output is correct
2 Correct 15 ms 21324 KB Output is correct
3 Correct 18 ms 26180 KB Output is correct
4 Correct 23 ms 31148 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 14 ms 16572 KB Output is correct
7 Correct 15 ms 21324 KB Output is correct
8 Correct 18 ms 26180 KB Output is correct
9 Correct 23 ms 31148 KB Output is correct
10 Correct 7 ms 7488 KB Output is correct
11 Correct 6 ms 7320 KB Output is correct
12 Correct 9 ms 12536 KB Output is correct
13 Correct 10 ms 13516 KB Output is correct
14 Correct 18 ms 22116 KB Output is correct
15 Correct 16 ms 22348 KB Output is correct
16 Correct 31 ms 33752 KB Output is correct
17 Correct 40 ms 39856 KB Output is correct
18 Correct 22 ms 31092 KB Output is correct