Submission #521057

#	Time	Username	Problem	Language	Result	Execution time	Memory
521057		Vladth11	Vještica (COCI16_vjestica)	C++14	160 / 160	110 ms	708 KiB

vjestica

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const int NMAX = 16;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 21;

int dp[(1 << NMAX)];
int cnt[NMAX][26];

int lcp(int a){
    int sol = 0;
    for(int j = 0; j < 26; j++){
        int minim = 2e9;
        for(int i = 0; i < NMAX; i++){
            if((a & (1 << i)))
                minim = min(minim, cnt[i][j]);
        }
        sol += minim;
    }
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < (1 << n); i++)
        dp[i] = 1e9;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(auto x : s) {
            cnt[i][x - 'a']++;
        }
        dp[(1 << i)] = s.size();
    }
    for(int mask = 0; mask < (1 << n); mask++) {
        int p = lcp(mask);
        for(int submask = (mask - 1) & mask; submask > 0; submask = ((submask - 1) & mask)) {
            dp[mask] = min(dp[mask], dp[submask] + dp[(submask ^ mask)] - p);
        }
    }
    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

Compilation message (stderr)

vjestica.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   12 | const int INF = (1LL << 60);
      |                 ~~~~~^~~~~~

• Subtask 1: 160 / 160