oj.uz

Submission #42754

# Submission time Handle Problem Language Result Execution time Memory
42754 2018-03-03T19:15:45 Z ekrem Vještica (COCI16_vjestica) C++
160 / 160
 212 ms 4956 KB 
/*
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 = 1e5 + 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 dp[bit] = 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

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;}
                                          ^

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4320 KB Output is correct
3 Correct 5 ms 4320 KB Output is correct
4 Correct 192 ms 4320 KB Output is correct
5 Correct 199 ms 4536 KB Output is correct
6 Correct 204 ms 4700 KB Output is correct
7 Correct 212 ms 4892 KB Output is correct
8 Correct 206 ms 4956 KB Output is correct
9 Correct 212 ms 4956 KB Output is correct
10 Correct 207 ms 4956 KB Output is correct