제출 #1174827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174827		nuutsnoynton	Vještica (COCI16_vjestica)	C++20	160 / 160	1833 ms	1676 KiB

vjestica

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll dp[65538] = {0};
ll cnt[20][30] = {0};
int main() {
	ll n, m, r, x, mask1, s, mask2, pop_c, y, i, j, ans, t;

	cin >> n;
	
	string str[17];
	
	for (i = 0; i < 65536; i ++) dp[i] = 1e18;
	
	for (i = 0; i < n; i ++) {
		cin >> str[i];
		dp[1<< i] = str[i].size();
		for (j = 0; j < str[i].size(); j++) {
			cnt[i][str[i][j] - 'a'] ++;
		}
	}	
	
	for (i = 1; i < (1<< n); i ++) {
		pop_c = __builtin_popcount(i);
		if ( pop_c == 1) {
			continue;
		}
		
		vector < ll > v;
		for (j = 0; j < n; j ++) {
			r = (1<<j) & i;
			if ( r > 0) {
				v.push_back(j);
			}
		}
		
		for ( r = 1;  r+ 1< (1<<v.size());  r++) {
			mask1 = mask2 = 0;
			for (j = 0; j < v.size(); j ++) {
				s = (1<< j) & r;
				if ( s > 0) {
					mask1 = mask1 + (1<<(v[j]));
				}
				else mask2 = mask2 + (1<<(v[j]));
			}
		//	cout << mask1 << " " << mask2 << endl;
			dp[i] = min(dp[i], dp[mask1] + dp[mask2]);
		}
		ll cnt1[32];
		s = 0;
		for (j = 0; j < 30; j ++) cnt1[j] = 1e18;
		for ( r = 0; r < v.size(); r ++) {
			for ( j = 0; j < 26; j ++) {
				cnt1[j] = min(cnt1[j], cnt[v[r]][j]);
			}
		}
		for (j = 0;j < 26; j ++) {
//			if ( cnt1[j] == 1e18) continue;
			s = s + cnt1[j];
		}
	//	s = s * (pop_c - 1);
		dp[i] -= s;
//		cout <<v.size() << " " <<   i << " "<< dp[i] << endl;
	}
	
	cout << dp[(1<<n)- 1] + 1 << endl;
}

• Subtask 1: 160 / 160