Submission #1272717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272717		zNatsumi	Vještica (COCI16_vjestica)	C++20	160 / 160	119 ms	1128 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

int n, cnt[20][26], f[(1<<16) + 5], g[(1<<16) + 5];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    for(auto x : s) cnt[i][x - 'a'] += 1;
    f[1 << i] = s.size();
  }
  for(int msk = 1; msk < (1 << n); msk++){
    for(int x = 0; x < 26; x++){
      int tmp = 1'000'000'000;
      for(int i = 0; i < n; i++)
        if(msk >> i & 1) tmp = min(tmp, cnt[i][x]);
      g[msk] += tmp;
    }
  }

  for(int msk = 1; msk < (1 << n); msk++){
    if(__builtin_popcount(msk) == 1) continue;
    f[msk] = 1'000'000'000;
    for(int sub = msk; sub > 0; sub = (sub - 1) & msk)
      if(sub != msk) f[msk] = min(f[msk], f[sub] + f[msk ^ sub] - g[msk]);
  }
  cout << f[(1 << n) - 1] + 1 << "\n";

  return 0;
}

Compilation message (stderr)

vjestica.cpp: In function 'int32_t main()':
vjestica.cpp:25:14: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
   25 |       g[msk] += tmp;
      |       ~~~~~~~^~~~~~
vjestica.cpp:21:22: note: within this loop
   21 |     for(int x = 0; x < 26; x++){
      |                    ~~^~~~

• Subtask 1: 160 / 160