oj.uz

Submission #499883

# Submission time Handle Problem Language Result Execution time Memory
499883 2021-12-29T21:49:49 Z Carmel_Ab1 Anagramistica (COCI21_anagramistica) C++17
110 / 110
 23 ms 33160 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
void solve() {
    int n,k;
    cin >> n >> k;
    vector<string>s(n);
    read(s);

    map<string,int>mp;
    for(int i=0; i<n; i++){
        sort(all(s[i]));
        mp[s[i]]++;
    }
    ll mod=1e9+7;

    vvl C(2001,vl(2001));
    for(int i=0 ;i<=2000; i++){
        C[i][0]=1;
        for(int j=1; j<=i; j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }

    vi a;
    for(auto x:mp)a.pb(x.second);
    n=a.size();


    vvl dp(n+1,vl(k+1));

    reverse(all(a));
    a.pb(0);
    reverse(all(a));

    dp[0][0]=1;
    for(int i=1; i<=n; i++){
        for(int c=0; c<=a[i]; c++)
            for(int j=0; j<=k; j++){
                if(j>=C[c][2])
                    dp[i][j]=(dp[i][j]+dp[i-1][j-C[c][2]]*C[a[i]][c])%mod;
            }
    }
    out(dp[n][k])
}

Compilation message

anagramistica.cpp: In function 'void usaco(std::string)':
anagramistica.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
anagramistica.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31644 KB Output is correct
2 Correct 17 ms 31704 KB Output is correct
3 Correct 16 ms 31636 KB Output is correct
4 Correct 17 ms 31644 KB Output is correct
5 Correct 17 ms 31652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31820 KB Output is correct
2 Correct 19 ms 31904 KB Output is correct
3 Correct 17 ms 31692 KB Output is correct
4 Correct 17 ms 31820 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31644 KB Output is correct
2 Correct 17 ms 31704 KB Output is correct
3 Correct 16 ms 31636 KB Output is correct
4 Correct 17 ms 31644 KB Output is correct
5 Correct 17 ms 31652 KB Output is correct
6 Correct 19 ms 31820 KB Output is correct
7 Correct 19 ms 31904 KB Output is correct
8 Correct 17 ms 31692 KB Output is correct
9 Correct 17 ms 31820 KB Output is correct
10 Correct 19 ms 32172 KB Output is correct
11 Correct 17 ms 31724 KB Output is correct
12 Correct 17 ms 31780 KB Output is correct
13 Correct 17 ms 31688 KB Output is correct
14 Correct 18 ms 31820 KB Output is correct
15 Correct 17 ms 31720 KB Output is correct
16 Correct 22 ms 33160 KB Output is correct
17 Correct 23 ms 31896 KB Output is correct
18 Correct 19 ms 31804 KB Output is correct