Submission #541848

#	Time	Username	Problem	Language	Result	Execution time	Memory
541848		new_acc	Vještica (COCI16_vjestica)	C++14	160 / 160	1658 ms	1352 KiB

vjestica

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll M=1e6+10;
const int N=1e5+10;
const ll SS=1<<20;
const ll INFi=1e9;
const ll INFl=1e12;
const int k=17;
int t[k][26],dl[N];
int dp[(1<<k)+1];
void solve(){
	int n;
	cin>>n;
	int xd=0;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++) t[i][int(s[j])-96]++;
		dl[i]=s.size();
	}
	for(int i=1;i<(1<<n);i++){
		if(__builtin_popcount(i)==1){
			dp[i]=0;
			continue;
		}
		int ile=0;
		for(int k=1;k<=26;k++){
			int mini=INFi;
			for(int j=0;j<n;j++){
				if(!((1<<j)&i)) continue;
				mini=min(mini,t[j+1][k]);
			}
			ile+=mini;
		}
		vi pom;
		int sum=0;
		for(int j=0;j<n;j++) if((1<<j)&i) sum+=dl[j+1],pom.push_back(j);
		if(sum==ile*__builtin_popcount(i)){
			dp[i]=ile*(__builtin_popcount(i)-1);
			continue;
		}
		for(int j=1;j<(1<<pom.size())-1;j++){
			int mask=0;
			for(int k=0;k<pom.size();k++) if((1<<k)&j) mask+=(1<<pom[k]);
			dp[i]=max(dp[i],dp[mask]+dp[i-mask]+ile);
		}
	}
	int res=0;
	for(int i=1;i<=n;i++) res+=dl[i];
	cout<<res-dp[(1<<n)-1]+1<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

vjestica.cpp: In function 'void solve()':
vjestica.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<s.size();j++) t[i][int(s[j])-96]++;
      |               ~^~~~~~~~~
vjestica.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int k=0;k<pom.size();k++) if((1<<k)&j) mask+=(1<<pom[k]);
      |                ~^~~~~~~~~~~
vjestica.cpp:20:6: warning: unused variable 'xd' [-Wunused-variable]
   20 |  int xd=0;
      |      ^~

• Subtask 1: 160 / 160