oj.uz

Submission #219691

# Submission time Handle Problem Language Result Execution time Memory
219691 2020-04-06T01:16:08 Z MohamedAhmed04 Vještica (COCI16_vjestica) C++14
0 / 160
 79 ms 1656 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 17 ;

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

bool cmp(string &a , string &b)
{
	return a.size() < b.size() ;
}

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']++ ;
	}
	sort(arr , arr + n , cmp) ;
	for(int i = 0 ; i < n ; ++i)
	{
		dp[1 << i] = arr[i].size() ;
		for(int j = i+1 ; j < n ; ++j)
		{
			pref[i][j] = 1 ;
			for(int k = 0 ; k < 26 ; ++k)
			{
				if(freq[i][k] > freq[j][k])
					pref[i][j] = 0 ;
			}
		}
	}
	for(int mask = 1 ; mask < (1 << n) ; ++mask)
	{
		if(__builtin_popcount(mask) == 1)
			continue ;
		dp[mask] = 1e9 ;
		int prv = -1 , Max = 0 ;
		bool can = 1 ;
		for(int i = 0 ; i < n ; ++i)
		{
			if((mask & (1 << i)))
			{
				if(prv != -1 && !pref[prv][i])
					can = 0 ;
				prv = i ;
				Max = arr[i].size() ;
			}
		}
		if(can)
		{
			dp[mask] = Max ;
			continue ;
		}
		for(int sub = mask ; sub ; sub = (sub-1) & mask)
			dp[mask] = min(dp[mask] , dp[sub] + dp[mask ^ sub]) ;
	}
	return cout<<dp[(1 << n) - 1]+1<<"\n" , 0 ;
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Incorrect 75 ms 632 KB Output isn't correct
5 Incorrect 75 ms 760 KB Output isn't correct
6 Incorrect 76 ms 1144 KB Output isn't correct
7 Incorrect 79 ms 1528 KB Output isn't correct
8 Incorrect 79 ms 1656 KB Output isn't correct
9 Incorrect 78 ms 1528 KB Output isn't correct
10 Incorrect 77 ms 1528 KB Output isn't correct