oj.uz

Submission #679888

# Submission time Handle Problem Language Result Execution time Memory
679888 2023-01-09T15:17:44 Z Shadii_usf Anagramistica (COCI21_anagramistica) C++14
0 / 110
 39 ms 32080 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn =  2e3 + 10, mod = 1e9 + 7;
long long dp[maxn][maxn] , c[maxn][maxn];
int main(){
    int n , k , cnt = 1;
    string a[maxn];
    bool mark[maxn] , markk[maxn];
    vector <int> v;
    cin >> n >> k;
    for(int i=1 ; i<=n ; i++){
        cin >> a[i];
    }
    for(int i=1 ; i<=n ; i++){
        for(int j = 0 ; j<a[i].size() ; j++){
            mark[a[i][j] - 'a'] = true;
        }
        for(int j = 1 ; j<=n ; j++){
            bool x = true;
            if(!markk[j] && j != i){
                for(int k = 0 ; k<a[j].size() ; k++){
                    if(!mark[a[j][k] - 'a']){
                        x = false;
                        break;
                    }
                }
                if(x){
                    cnt++;
                    markk[j] = true;
                }
            }
        }
        if(!markk[i]){
            v.push_back(cnt);
            markk[i] = true;
        }
        for(int j = 0 ; j<a[i].size() ; j++){
            mark[a[i][j] - 'a'] = false;
        }
        cnt = 1;
    }
    for(int i = 0 ; i<maxn ; i++){
        c[0][i] = 1;
    }
    for(int i=1 ; i<maxn ; i++){
        for(int j=1 ; j<maxn ; j++){
            c[i][j] = c[i - 1][j - 1] + c[i][j - 1];
            c[i][j] %= mod;
        }
    }
    for(int i=0 ; i<=v[0] ; i++){
        int num = (i * (i - 1))/2;
        dp[0][num] = c[i][v[0]];
    }
    int sizee = v.size();
    for(int i=1 ; i<sizee ; i++){
        for(int j=0 ; j<=k ; j++){
            int m = 0;
            while((m * (m - 1))/2 <= j && m <= v[i]){
                dp[i][j] += (dp[i - 1][j - (m * (m - 1))/2] * c[m][v[i]] % mod);
                dp[i][j] %= mod;
                m++;
            }
        }
    }
    cout << (dp[v.size() - 1][+k] == 0 ? -1 : dp[v.size() - 1][k]);
}

Compilation message

anagramistica.cpp: In function 'int main()':
anagramistica.cpp:15:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int j = 0 ; j<a[i].size() ; j++){
      |                         ~^~~~~~~~~~~~
anagramistica.cpp:21:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                 for(int k = 0 ; k<a[j].size() ; k++){
      |                                 ~^~~~~~~~~~~~
anagramistica.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0 ; j<a[i].size() ; j++){
      |                         ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 32080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 31864 KB Output isn't correct
2 Halted 0 ms 0 KB -