Submission #42752

# Submission time Handle Problem Language Result Execution time Memory
42752 2018-03-03T19:03:12 Z ekrem Vještica (COCI16_vjestica) C++
48 / 160
21 ms 4964 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 = 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

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 2092 KB Output is correct
4 Runtime error 5 ms 3692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 7 ms 3908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 4396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 21 ms 4868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 20 ms 4964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 4964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 19 ms 4964 KB Execution killed with signal 11 (could be triggered by violating memory limits)