Submission #504090

#	Time	Username	Problem	Language	Result	Execution time	Memory
504090		kostia244	Vještica (COCI16_vjestica)	C++17	160 / 160	154 ms	1616 KiB

vjestica

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int N = 16;
int n, cnt[N][26], dp[1<<N], val[1<<N], sum[1<<N];
int f(int msk) {
	if(!msk) return 0;
	if(dp[msk] != -1) return dp[msk];
	dp[msk] = sum[msk] - val[msk]*__builtin_popcount(msk);
	for(int i = (msk-1)&msk; i; i = (i-1)&msk) {
		dp[msk] = min(dp[msk], f(i)+f(msk^i)+val[i]+val[msk^i]-2*val[msk]);
	}
	return dp[msk];
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	cin >> n;
	string s;
	for(int i = 0; i < n; i++) {
		cin >> s;
		for(auto c : s) cnt[i][c-'a']++;
	}
	for(int i = 1; i < 1<<n; i++) {
		array<int, 26> c;
		c.fill(1<<30);
		for(int j = 0; j < n; j++) if( (i>>j) & 1 ) {
			for(int z = 0; z < 26; z++) {
				c[z] = min(c[z], cnt[j][z]);
				sum[i] += cnt[j][z];
			}	
		}
		for(int j = 0; j < 26; j++)
			val[i] += c[j];
	}
	memset(dp, -1, sizeof dp);
	cout << 1+val[(1<<n)-1]+f((1<<n)-1) << '\n';
}

• Subtask 1: 160 / 160