/*
ID: ekrem
LANG: C++
TASK:
*/
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define foreach(kk,gg) for(__typeof(gg.begin())kk=gg.begin();kk!=gg.end();kk++)
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define SET(a, b) memset(a, b, sizeof a)
#define heap priority_queue
#define orta (bas+son>>1)
#define endll puts("")
#define mp make_pair
#define pb push_back
#define sag (k+k+1)
#define sol (k+k)
#define endl '\n'
#define nd second
#define st first
#define y1 ekrem
#define y2 merke
typedef int don;
#define int long long int
inline int read(){int x;scanf(" %lld",&x);return x;}
typedef pair < int , int > ii;
typedef vector < int > vi;
typedef vector < ii > vii;
const int inf = 1e9 + 7;
const int linf = 1e18 + 7;
const int N = 4e4 + 5;
int n, dp[N], c[20][30], h[30];
string s[N];
int bul(int bit){
int top = 0;
FOR(i, 0, 'z' - 'a')h[i] = inf;
FOR(i, 0, n)
if(bit&(1<<i))
FOR(ch, 0, 'z' - 'a')
h[ch] = min(h[ch], c[i][ch]);
FOR(i, 0, 'z' - 'a')
if(h[i] < inf)
top += h[i];
return top;
}
int coz(int bit){
if(dp[bit] != -1)
return dp[bit];
int bas = bul(bit);
if((bit & (-bit)) == bit)
return bas;
int ans = inf;
for(int i = (bit - 1)&bit; i > 0; i = (i - 1)&bit)
ans = min(ans, coz(i) + coz(bit^i) - bas);
return dp[bit] = ans;
}
don main(){
// freopen("input.in", "r", stdin);freopen("input.out", "w", stdout);
SET(dp, -1);
n = read() - 1;
FOR(i, 0, n)
cin >> s[i];
FOR(i, 0, n)
FOR(j, 0, s[i].length() - 1)
c[i][s[i][j] - 'a']++;
cout << coz((1<<(n + 1)) - 1) + 1 << endl;
return 0;
}
Compilation message
vjestica.cpp: In function 'don main()':
vjestica.cpp:28:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
^
vjestica.cpp:91:3: note: in expansion of macro 'FOR'
FOR(j, 0, s[i].length() - 1)
^
vjestica.cpp: In function 'long long int read()':
vjestica.cpp:45:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
inline int read(){int x;scanf(" %lld",&x);return x;}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1948 KB |
Output is correct |
| 4 |
Runtime error |
4 ms |
3732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
8 ms |
4172 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
13 ms |
4828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
26 ms |
5488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
21 ms |
6244 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
19 ms |
6632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
19 ms |
6980 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
