Submission #679888

#TimeUsernameProblemLanguageResultExecution timeMemory
679888Shadii_usfAnagramistica (COCI21_anagramistica)C++14
0 / 110
39 ms32080 KiB
#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 (stderr)

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++){
      |                         ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...