Submission #167677

#TimeUsernameProblemLanguageResultExecution timeMemory
167677EntityITVještica (COCI16_vjestica)C++14
160 / 160
184 ms760 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define sz(x) ( (int)(x).size() ) #define fi first #define se second using LL = long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() ); const int inf = 1e9; int n; vector<int> f; vector<vector<int> > cnt; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i) { string s; cin >> s; cnt.emplace_back(vector<int>(26, 0) ); for (char c : s) ++cnt.back()[c - 'a']; } f.assign(1 << n, inf); f[0] = 0; for (int mask = 1; mask < (1 << n); ++mask) { if (__builtin_popcount(mask) == 1) { f[mask] = accumulate(all(cnt[__lg(mask)]), 0); continue ; } int tmp = 0; for (int ascii = 0; ascii < 26; ++ascii) { int mn = inf; for (int i = 0; i < n; ++i) if ( (mask >> i) & 1) mn = min(mn, cnt[i][ascii]); tmp += mn; } for (int sMask = mask; sMask > 0; sMask = (sMask - 1) & mask) if (sMask != mask) { f[mask] = min(f[mask], f[sMask] + f[mask ^ sMask] - tmp); } } cout << f[(1 << n) - 1] + 1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...