Submission #52000

#	Time	Username	Problem	Language	Result	Execution time	Memory
52000		Adhyyan1252	Vještica (COCI16_vjestica)	C++11	160 / 160	372 ms	3448 KiB

vjestica

#include<bits/stdc++.h>

using namespace std;
#define NMAX 16
string s[NMAX];
vector<vector<int> > f;
int n;
int  dp[(1<<NMAX)];

int rec(int mask){
	if(dp[mask] != -1) return dp[mask];
	
	int lcp = 0;
	for(int i = 0; i < 26; i++){
		int cur = INT_MAX;
		for(int j = 0; j < n; j++){
			if(mask&(1<<j))
				cur = min(cur, f[j][i]);
		}
		lcp += cur;
	}
	
	dp[mask] = INT_MAX;
	for(int sub = (mask-1)&mask; sub > 0; sub = (sub-1)&mask){
		dp[mask] = min(dp[mask], rec(sub) + rec(sub^mask) - lcp);
	}
	return dp[mask];
}

int main(){
	cin>>n;
	f.resize(n, vector<int>(26, 0));
	for(int i = 0; i < n; i++){
		cin>>s[i];
		for(int j = 0; j < s[i].length(); j++){
			f[i][s[i][j]-'a']++;
		}
	}
	for(int i = 0; i < (1<<n); i++) dp[i] = -1;
	dp[0] = 0;
	for(int i = 0; i < n; i++){
		dp[(1<<i)] = s[i].length();
	}
	cout<<rec((1<<n)-1) + 1<<endl;
//	for(int i = 0; i < (1<<n); i++){
//		cout<<i<<" : "<<dp[i]<<endl;
//	}
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < s[i].length(); j++){
                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 160 / 160