Submission #1127553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127553		VinhLuu	Vještica (COCI16_vjestica)	C++17	160 / 160	95 ms	1348 KiB

vjestica

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

const int N = 22;
const int oo = 1e9;

int g[(1 << 17)], sz[22], t[(1 << 17)], n, f[(1 << 17)], cnt[28][N];

#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")) {
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n;
  for(int i = 1; i <= n; i ++) {
    string s; cin >> s;
    for(auto j : s) cnt[(int)(j - 'a' + 1)][i]++;
    sz[i] = (int)s.size();
  }
  for(int msk = 1; msk < (1 << n); msk ++) {
    vector<int> vr;
    for(int j = 1; j <= n; j ++) if(msk >> (j - 1) & 1) vr.push_back(j);
    for(int i = 1; i <= 26; i ++) {
      int Min = 1e9;
      for(auto j : vr) Min = min(Min, cnt[i][j]);
//      cerr << msk << " " << i << " " << Min << " f\n";
      g[msk] += Min;
    }
    for(auto j : vr) t[msk] += sz[j];

    f[msk] = t[msk] + (1 - (int)vr.size()) * g[msk];
//     cerr << bitset<4>(msk) << " " << g[msk] << " " << t[msk] << " " << f[msk] << "\n";
  }

  for(int msk = 1; msk < (1 << n); msk ++) {
//    cerr << msk << " " << f[2] << " e\n";

    for(int sub = msk; sub > 0; sub = (sub - 1) & msk) {
      int nxt = (msk ^ sub);
      if(!nxt) continue;
      f[msk] = min(f[msk], f[sub] + f[nxt] - g[msk]);
//      if(f[msk] < 0) {
//        cerr << bitset<4>(msk) << " " << bitset<4>(sub) << " " << sub<< " " << bitset<4>(nxt) << " " << f[sub] << " " << f[nxt] << " " << g[msk] << " l\n";
//      }
    }
//    cerr << msk << " " << f[((1 << n) - 1)] << " r\n";
  }
  cout << f[(1 << n) - 1] + 1;
}
#endif // lpv

Compilation message (stderr)

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

• Subtask 1: 160 / 160