Submission #167684

#	Time	Username	Problem	Language	Result	Execution time	Memory
167684		atoiz	Vještica (COCI16_vjestica)	C++14	160 / 160	97 ms	1272 KiB

vjestica

/*input
3 a ab c
*/

#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <utility>
#include <tuple>
#include <climits>
#include <fstream>
#include <bitset>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <random>
#include <chrono>
#include <ios>
#include <iomanip>
#include <functional>

using namespace std;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size())
#define ALL(a) begin(a), end(a)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define fi first
#define se second

// start of code

signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;
	vector<vector<int>> cnt(N, vector<int>(26, 0));
	FOR(i, 0, N - 1) {
		string str;
		cin >> str;
		FORA(ch, str) {
			++cnt[i][(int) ch - 'a'];
		}
	}

	static const int INF = 1e9;
	vector<int> dp(1 << N, INF);
	FOR(mask, 1, (1 << N) - 1) {
		if (__builtin_popcount(mask) == 1) {
			int i = __lg(mask);
			dp[mask] = accumulate(cnt[i].begin(), cnt[i].end(), 0);
			continue;
		}

		for (int submask = mask & (mask - 1); submask; submask = mask & (submask - 1)) {
			dp[mask] = min(dp[mask], dp[mask ^ submask] + dp[submask]);
		}

		vector<int> tmp(26, INF);
		FOR(i, 0, N - 1) if ((mask >> i) & 1) FOR(j, 0, 25) {
			tmp[j] = min(tmp[j], cnt[i][j]);
		}
		dp[mask] -= accumulate(tmp.begin(), tmp.end(), 0);
	}

	cout << dp[(1 << N) - 1] + 1 << endl;

	return 0;
}

• Subtask 1: 160 / 160