oj.uz

Submission #167684

# Submission time Handle Problem Language Result Execution time Memory
167684 2019-12-09T14:53:13 Z atoiz Vještica (COCI16_vjestica) C++14
160 / 160
 97 ms 1272 KB 
/*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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 94 ms 632 KB Output is correct
5 Correct 95 ms 760 KB Output is correct
6 Correct 95 ms 892 KB Output is correct
7 Correct 97 ms 1144 KB Output is correct
8 Correct 97 ms 1272 KB Output is correct
9 Correct 96 ms 1172 KB Output is correct
10 Correct 96 ms 1200 KB Output is correct