oj.uz

Submission #712002

# Submission time Handle Problem Language Result Execution time Memory
712002 2023-03-17T22:55:17 Z Doncho_Bonboncho Vještica (COCI16_vjestica) C++14
160 / 160
 98 ms 5352 KB 
#include <algorithm>
#include <bits/stdc++.h>
#include <cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 20;
const int ALF = 26;
const int INF = 1e9;
const int mod = 1e9 + 7;

int num[MAX_N][ALF];
std::string str[MAX_N];

int dp[1<<MAX_N];


int calcPref( int mask ){

	int currNum[ALF];
	std::fill( currNum, currNum + ALF , INF );

	for( int i=0 ; i<MAX_N ; i++ ){
		if( mask & (1<<i) ){
			for( int j=0 ; j<ALF ; j++ ){
				currNum[j] = std::min( currNum[j], num[i][j] );
			}
		}
	}
	ll nas = 0;
	for( int i=0 ; i<ALF ; i++ ) nas += currNum[i];
	return nas;
}

int sol( int mask ){
	//int &ret = dp[mask];
	if( dp[mask] != -1 ) return dp[mask];
	int pref = calcPref( mask );
	if( (mask&-mask) == mask ) return dp[mask] = pref;
	int currNas = INF;
	for( int i = (mask-1)&mask ; i > 0 ; i = (i-1)&mask ){
		currNas = std::min( currNas, sol(i) + sol( mask ^ i ) - pref );
	}
	return dp[mask] = currNas;
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	for( int i=0 ; i<n ; i++ ){
		std::cin>>str[i];
		for( int j=0 ; j<str[i].size() ; j++ )
			num[i][str[i][j]-'a'] ++;
	}


	std::memset(dp, -1, sizeof(dp));
	
	std::cout<<sol( (1<<n)-1 )+1<<"\n";

	return 0;
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for( int j=0 ; j<str[i].size() ; j++ )
      |                  ~^~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 96 ms 4436 KB Output is correct
5 Correct 90 ms 4576 KB Output is correct
6 Correct 97 ms 4976 KB Output is correct
7 Correct 92 ms 5260 KB Output is correct
8 Correct 94 ms 5332 KB Output is correct
9 Correct 95 ms 5332 KB Output is correct
10 Correct 98 ms 5352 KB Output is correct