Submission #490161

#	Time	Username	Problem	Language	Result	Execution time	Memory
490161		Killer2501	Vještica (COCI16_vjestica)	C++14	160 / 160	91 ms	1472 KiB

vjestica

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "test"
#define pii pair<pll, pll>
using namespace std;
using ll = int;
const int  N = 16;
const ll mod = 1e8+7;
const ll base = 113;
const ll inf = 1e9;
ll m, n, t, k, a[N][N*2], tong, d[N], b[N*2], h[N], ans, dp[(1<<N)], cnt[(1<<N)];
vector<ll> adj[N];
vector<ll> kq, ask[N];
ll pw(ll k, ll n, ll md)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n&1)total = total * k % md;
		k = k * k % md;
	}
	return total;
}
string s;
void sol()
{
    cin >> n;
    for(int i = 0; i < n;i ++)
    {
        cin >> s;
        for(int j = 0; j < s.length(); j ++)++a[i][s[j]-'a'];
    }
    for(int i = 0; i < (1<<n); i ++)
    {
        fill_n(b, 26, inf);
        for(int j = 0; j < n; j ++)
        {
            if((i >> j) & 1)
                for(int p = 0; p < 26; p ++)b[p] = min(b[p], a[j][p]);
        }
        for(int j = 0; j < 26; j ++)cnt[i] += b[j];
    }
    for(int i = 1; i < (1<<n); i ++)
    {
        if(__builtin_popcount(i) == 1)dp[i] = cnt[i];
        else
        {
            dp[i] = inf;
            for(int j = i; j; j = (j - 1) & i)
            {
                dp[i] = min(dp[i], dp[j]+dp[i^j]-cnt[i]);
            }
        }
    }
    cout << dp[(1<<n)-1]+1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

vjestica.cpp: In function 'void sol()':
vjestica.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j = 0; j < s.length(); j ++)++a[i][s[j]-'a'];
      |                        ~~^~~~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
vjestica.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160