Submission #1174809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174809		Nomio	Vještica (COCI16_vjestica)	C++20	48 / 160	2097 ms	7748 KiB

vjestica

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	string s[n];
	vector<int> dp((1 << n), 1e9);
	int cnt[(1 << n)][26] {};
	for(int i = 0; i < n; i++) {
		cin >> s[i];
		dp[(1 << i)] = s[i].size();
		for(int j = 0; j < s[i].size(); j++) {
			cnt[(1 << i)][s[i][j] - 'a']++;
		}
	}
	dp[0] = 0; 
	for(int i = 1; i < (1 << n); i++) {
		vector<int> v;
		for(int j = 0; j < n; j++) {
			if((i >> j) % 2 == 1) v.push_back(j);
		}
		int K = v.size();
		for(int j = 1; j < (1 << K); j++) {
			int a = i, b = 0;
			for(int l = 0; l < K; l++) {
				if((j >> l) % 2 == 1) {
					a -= (1 << v[l]);
					b += (1 << v[l]);
					int s = 0;
					for(int k = 0; k < 26; k++) {
						s += min(cnt[a][k], cnt[b][k]);
					}
					if(dp[a] + dp[b] - s < dp[i]) {
						dp[i] = min(dp[i], dp[a] + dp[b] - s);
						for(int k = 0; k < 26; k++) {
							cnt[i][k] = min(cnt[a][k], cnt[b][k]);
						}
					}
				}
			}
		}
	}
	cout << dp[(1 << n) - 1] + 1 << '\n';
	return 0;
}

• Subtask 1: 48 / 160