Submission #1174791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174791		Nomio	Vještica (COCI16_vjestica)	C++20	96 / 160	21 ms	7752 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; // 1
	for(int i = 1; i < (1 << n); i++) {
		for(int j = 0; j < n; j++) {
			if((i >> j) % 2 == 1) {
				int a = i - (1 << j);
				int b = (1 << j);
				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: 96 / 160