oj.uz

Submission #504090

# Submission time Handle Problem Language Result Execution time Memory
504090 2022-01-09T18:01:14 Z kostia244 Vještica (COCI16_vjestica) C++17
160 / 160
 154 ms 1616 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int N = 16;
int n, cnt[N][26], dp[1<<N], val[1<<N], sum[1<<N];
int f(int msk) {
	if(!msk) return 0;
	if(dp[msk] != -1) return dp[msk];
	dp[msk] = sum[msk] - val[msk]*__builtin_popcount(msk);
	for(int i = (msk-1)&msk; i; i = (i-1)&msk) {
		dp[msk] = min(dp[msk], f(i)+f(msk^i)+val[i]+val[msk^i]-2*val[msk]);
	}
	return dp[msk];
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	cin >> n;
	string s;
	for(int i = 0; i < n; i++) {
		cin >> s;
		for(auto c : s) cnt[i][c-'a']++;
	}
	for(int i = 1; i < 1<<n; i++) {
		array<int, 26> c;
		c.fill(1<<30);
		for(int j = 0; j < n; j++) if( (i>>j) & 1 ) {
			for(int z = 0; z < 26; z++) {
				c[z] = min(c[z], cnt[j][z]);
				sum[i] += cnt[j][z];
			}	
		}
		for(int j = 0; j < 26; j++)
			val[i] += c[j];
	}
	memset(dp, -1, sizeof dp);
	cout << 1+val[(1<<n)-1]+f((1<<n)-1) << '\n';
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 572 KB Output is correct
4 Correct 149 ms 1100 KB Output is correct
5 Correct 149 ms 1172 KB Output is correct
6 Correct 151 ms 1384 KB Output is correct
7 Correct 149 ms 1564 KB Output is correct
8 Correct 154 ms 1616 KB Output is correct
9 Correct 151 ms 1568 KB Output is correct
10 Correct 149 ms 1576 KB Output is correct