oj.uz

Submission #220373

# Submission time Handle Problem Language Result Execution time Memory
220373 2020-04-07T18:48:24 Z MohamedAhmed04 Vještica (COCI16_vjestica) C++14
160 / 160
 135 ms 1668 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 17 ;

string arr[MAX] ;
int freq[MAX][27] , dp[(1 << MAX)] ;

int  n ;

int commonpref(int mask)
{
	int sum = 0 ;
	for(int i = 0 ; i < 26 ; ++i)
	{
		int cnt = -1 ;
		for(int j = 0 ; j < n ; ++j)
		{
			if(!(mask & (1 << j))) 
				continue ;
			if(cnt == -1)
				cnt = freq[j][i] ;
			else
				cnt = min(cnt , freq[j][i]) ;
		}
		sum += max(cnt , 0) ;
	}
	return sum ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>arr[i] ;
		for(auto &c : arr[i])
			freq[i][c-'a']++ ;
	}
	for(int mask = 1 ; mask < (1 << n) ; ++mask)
	{
		dp[mask] = 1e9 ;
		int x = commonpref(mask) ;
		int Max = -1 ;
		for(int i = 0 ; i < n ; ++i)
		{
			if((mask & (1 << i)))
				Max = max(Max , (int)arr[i].size()) ;
		}
		if(Max == x)
		{
			dp[mask] = x ;
			continue ;
		}
		for(int sub = mask ; sub ; sub = (sub-1) & mask)
			dp[mask] = min(dp[mask] , dp[sub] + dp[mask ^ sub] - x) ;
	}
	return cout<<dp[(1 << n) - 1]+1<<"\n" , 0 ;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 122 ms 632 KB Output is correct
5 Correct 126 ms 760 KB Output is correct
6 Correct 127 ms 1252 KB Output is correct
7 Correct 125 ms 1400 KB Output is correct
8 Correct 125 ms 1528 KB Output is correct
9 Correct 128 ms 1540 KB Output is correct
10 Correct 135 ms 1668 KB Output is correct