Submission #1263040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263040		SmuggingSpun	Vještica (COCI16_vjestica)	C++20	160 / 160	80 ms	584 KiB

vjestica

#include<bits/stdc++.h>
#define taskname "F"
using namespace std;
const int INF = 1e9;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
int dp[1 << 16];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n;
	cin >> n;
	vector<vector<int>>cnt(26, vector<int>(n, 0));
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		for(char& c : s){
			cnt[c - 97][i]++;
		}
	}
	memset(dp, 0x0f, sizeof(dp));
	for(int mask = 1; mask < (1 << n); mask++){
		int sum = 0;
		for(int i = 0; i < 26; i++){
			int d = INF;
			for(int j = 0; j < n; j++){
				if(1 << j & mask){
					minimize(d, cnt[i][j]);
				}
			}
			sum += d;
		}	
		if(__builtin_popcount(mask) == 1){
			dp[mask] = sum;
			continue;
		}
		for(int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask){
			minimize(dp[mask], dp[sub] + dp[mask ^ sub] - sum);
		}
	}
	cout << dp[(1 << n) - 1] + 1;
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160