oj.uz

Submission #878528

# Submission time Handle Problem Language Result Execution time Memory
878528 2023-11-24T16:26:37 Z serifefedartar Vještica (COCI16_vjestica) C++17
160 / 160
 82 ms 1452 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 75 ms 972 KB Output is correct
5 Correct 79 ms 1112 KB Output is correct
6 Correct 75 ms 1116 KB Output is correct
7 Correct 76 ms 1452 KB Output is correct
8 Correct 76 ms 1360 KB Output is correct
9 Correct 76 ms 1364 KB Output is correct
10 Correct 82 ms 1360 KB Output is correct