Submission #412817

#TimeUsernameProblemLanguageResultExecution timeMemory
412817rqiVještica (COCI16_vjestica)C++14
160 / 160
731 ms1320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pi; #define mp make_pair #define f first #define s second #define pb push_back #define all(x) begin(x), end(x) const int MOD = 1e9+7; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void ckmin(int& a, int b){ a = min(a, b); } void ckmax(int& a, int b){ a = max(a, b); } int N; map<char, int> m[20]; int dp[1<<16]; int getLCP(int sub){ map<char, int> chars; bool isFirst = 1; for(int i = 0; i < N; i++){ if(!((sub>>i)&1)) continue; if(isFirst){ for(auto u: m[i]){ chars[u.f] = u.s; } isFirst = 0; } else{ for(auto u: chars){ ckmin(chars[u.f], m[i][u.f]); } } } // for(auto u: chars){ // cout << u.f << " " << u.s << "\n"; // } int sum = 1; for(auto u: chars){ sum+=u.s; } return sum; } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> N; for(int i = 0; i < N; i++){ string s; cin >> s; for(auto u: s){ m[i][u]++; } } for(int i = 1; i < (1<<N); i++){ //cout << "i: " << i << "\n"; int bit_num = 0; for(int j = 0; j < N; j++){ if((i>>j)&1){ bit_num++; } } if(bit_num == 1){ dp[i] = getLCP(i); } else{ dp[i] = MOD; for(int j = i;; j=((j-1)&i)){ if(i-j != 0 && j != 0){ ckmin(dp[i], dp[j]+dp[i-j]); } if(j == 0) break; } dp[i]-=getLCP(i); } } cout << dp[(1<<N)-1] << "\n"; // for(int i = 1; i < (1<<N); i++){ // cout << i << " " << dp[i] << "\n"; // } }
#Verdict Execution timeMemoryGrader output
Fetching results...