#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(), x.end()
#define bignum vector <int>
using namespace std;
const int N = 1e6 + 10101;
const int LOG = 16;
int n;
char s[N];
int a[20][26];
int cnt[1 << LOG][26];
int dp[1 << LOG];
int main() {
scanf ("%d", &n);
rep(i, 0, n - 1) {
scanf ("%s", s + 1);
int len = strlen(s + 1);
rep(j, 1, len) a[i][s[j] - 'a']++;
}
rep(mask, 1, (1 << n) - 1) {
rep(c, 0, 25) {
int y = n + 1;
rep(k, 0, n - 1)
if (((mask >> k) & 1)) y = min(y, a[k][c]);
cnt[mask][c] = y;
}
}
rep(mask, 1, (1 << n) - 1) {
if (__builtin_popcount(mask) == 1) {
dp[mask] = 0;
continue;
}
dp[mask] = 1e9;
int sub = ((mask - 1) & mask);
while (sub != 0) {
int x = sub;
int y = (mask ^ x);
int z = dp[x] + dp[y];
rep(c, 0, 25) z += (cnt[x][c] + cnt[y][c] - cnt[mask][c] - cnt[mask][c]);
assert(0 <= z);
//if (mask == ((1 << n) - 1)) {
// cat(z);
// cat(dp[x] + dp[y]);
// cat(x);
// cat(y);
//}
dp[mask] = min(dp[mask], z);
sub = ((sub - 1) & mask);
}
}
int res = dp[(1 << n) - 1];
rep(c, 0, 25) res += cnt[(1 << n) - 1][c];
printf ("%d\n", res + 1);
return 0;
}
Compilation message
vjestica.cpp: In function 'int main()':
vjestica.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &n);
~~~~~~^~~~~~~~~~
vjestica.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%s", s + 1);
~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
376 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
504 KB |
Output isn't correct |
| 4 |
Incorrect |
1367 ms |
7312 KB |
Output isn't correct |
| 5 |
Incorrect |
1364 ms |
7432 KB |
Output isn't correct |
| 6 |
Incorrect |
1379 ms |
7544 KB |
Output isn't correct |
| 7 |
Incorrect |
1392 ms |
7672 KB |
Output isn't correct |
| 8 |
Incorrect |
1368 ms |
7800 KB |
Output isn't correct |
| 9 |
Incorrect |
1385 ms |
7672 KB |
Output isn't correct |
| 10 |
Incorrect |
1376 ms |
7672 KB |
Output isn't correct |
