제출 #1272719

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

vjestica

#include <bits/stdc++.h>

using namespace std;

int n, cnt[20][26], f[1<<16], g[1<<16];

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 - 1) & msk; sub > 0; sub = (sub - 1) & msk)
      f[msk] = min(f[msk], f[sub] + f[msk ^ sub] - g[msk]);
  }
  cout << f[(1 << n) - 1] + 1 << "\n";

  return 0;
}

컴파일 시 표준 에러 (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