# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
547466 | 2022-04-10T19:15:40 Z | Olympia | Vještica (COCI16_vjestica) | C++17 | 97 ms | 8020 KB |
#include <cmath> #include <iostream> #include <set> #include <climits> #include <algorithm> #include <cassert> #include <vector> #include <iomanip> #include <type_traits> #include <string> #include <queue> #include <map> #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<string> vec(n); for (int i = 0; i < n; i++) { cin >> vec[i]; } int cnt[n][26]; int ans = 0; for (int i = 0; i < n; i++) { ans += vec[i].size(); for (int j = 0; j < 26; j++) cnt[i][j] = 0; for (int j = 0; j < vec[i].size(); j++) cnt[i][vec[i][j] - 'a']++; } int dp[(1 << n)]; int mn[(1 << n)][26]; int myMin[(1 << n)]; for (int i = 0; i < (1 << n); i++) { myMin[i] = 0; for (int j = 0; j < 26; j++) { mn[i][j] = INT_MAX; for (int k = 0; k < n; k++) { if (!(i & (1 << k))) continue; mn[i][j] = min(mn[i ^ (1 << k)][j], cnt[k][j]); } myMin[i] += mn[i][j]; } } for (int i = 0; i < (1 << n); i++) dp[i] = 0; for (int i = 0; i < n; i++) dp[(1 << i)] = 0; for (int msk = 1; msk < (1 << n); msk++) { if (__builtin_popcount(msk) == 1) continue; dp[msk] = 0; for (int sub_msk = msk; sub_msk; sub_msk = (sub_msk - 1) & msk) { dp[msk] = max(dp[msk], dp[sub_msk] + dp[msk ^ sub_msk] + myMin[msk]); } } cout << ans - dp[(1 << n) - 1] + 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 89 ms | 7508 KB | Output is correct |
5 | Correct | 93 ms | 7508 KB | Output is correct |
6 | Correct | 91 ms | 7764 KB | Output is correct |
7 | Correct | 93 ms | 7964 KB | Output is correct |
8 | Correct | 97 ms | 8020 KB | Output is correct |
9 | Correct | 95 ms | 8020 KB | Output is correct |
10 | Correct | 96 ms | 8020 KB | Output is correct |