oj.uz

Submission #202305

# Submission time Handle Problem Language Result Execution time Memory
202305 2020-02-15T08:53:21 Z Saboon Vještica (COCI16_vjestica) C++14
160 / 160
 203 ms 1528 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 16 + 5;

int a[20][30], b[30];
int dp[(1 << 16) + 10], lcp[(1 << 16) + 10];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int len = 0;
	for (int i = 0; i < n; i++){
		string s;
		cin >> s;
		for (int mask = 0; mask < (1 << n); mask++)
			if (mask & (1 << i))
				dp[mask] += (int)s.size();
		len += (int)s.size();
		for (int j = 0; j < (int)s.size(); j++)
			a[i][(int)s[j] - 'a'] ++;
	}
	for (int mask = 1; mask < (1 << n); mask ++){
		for (int j = 0; j < 26; j++)
			b[j] = len;
		for (int j = 0; j < n; j++)
			if (mask & (1 << j))
				for (int x = 0; x < 26; x++)
					b[x] = min(a[j][x], b[x]);
		for (int i = 0; i < 26; i++)
			lcp[mask] += b[i];
	}
	dp[0] = 0;
	for (int mask = 0; mask < (1 << n); mask++){
		for (int sub = mask; sub; sub = (sub - 1) & mask){
			if (mask == sub)
				continue;
			dp[mask] = min(dp[mask], dp[sub] + dp[mask ^ sub] - lcp[mask]);
		}
	}
	cout << dp[(1 << n) - 1] + 1 << '\n';
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 201 ms 888 KB Output is correct
5 Correct 198 ms 1144 KB Output is correct
6 Correct 194 ms 1144 KB Output is correct
7 Correct 200 ms 1524 KB Output is correct
8 Correct 199 ms 1400 KB Output is correct
9 Correct 203 ms 1368 KB Output is correct
10 Correct 200 ms 1528 KB Output is correct