# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42752 | ekrem | Vještica (COCI16_vjestica) | C++98 | 21 ms | 4964 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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, (int)s[i].length() - 1)
c[i][s[i][j] - 'a']++;
cout << coz((1<<(n + 1)) - 1) + 1 << endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |