Submission #878528

#	Time	Username	Problem	Language	Result	Execution time	Memory
878528		serifefedartar	Vještica (COCI16_vjestica)	C++17	160 / 160	82 ms	1452 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 21;
const ll MAXN = 2e4 + 100;

int cnt[16][26], dp[(1<<16)], pref[(1<<16)];
int main() {
	fast
	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (auto u : s)
			cnt[i][u - 'a']++;
	}

	for (int i = 1; i < (1<<N); i++) {
		bool here = false;
		vector<int> mns(26, -1); 
		for (int j = 0; j < N; j++) {
			if ((1<<j) & i) {
				if (!here) {
					for (int q = 0; q < 26; q++)
						mns[q] = cnt[j][q];
				} else {
					for (int q = 0; q < 26; q++)
						mns[q] = min(cnt[j][q], mns[q]);
				}
				here = true;
			}
		}
		int sum = 0;
		for (auto u : mns)
			sum += u;
		pref[i] = sum;
	}

	for (int i = 0; i < (1<<N); i++)
		dp[i] = 1e8;
	for (int i = 0; i < N; i++)
		dp[(1<<i)] = pref[(1<<i)];

	for (int i = 1; i < (1<<N); i++) {
		int msk = ((1<<N)-1) & i;
		while (msk) {
			dp[i] = min(dp[i], dp[msk] + dp[i ^ msk] - pref[i]);
			msk = (msk - 1) & i;
		}
	}

	cout << dp[(1<<N) - 1] + 1 << "\n";
}

• Subtask 1: 160 / 160