Submission #169199

#	Time	Username	Problem	Language	Result	Execution time	Memory
169199		_qVp_	Vještica (COCI16_vjestica)	C++14	160 / 160	1993 ms	1784 KiB

vjestica

#include<bits/stdc++.h>
using namespace std;

const int mN = 16;
const int mB = (1<<mN);
const int oo = 1e9;
string s[mN];
int cnt[mN][26];
int common[mB];
int F[mB];

int dp(int n) {
    if (n == 0) return 0;
    if (F[n] > -1) return F[n];
    int Min = oo;
    for (int x=1; x<n; x++) if ((x|n) == n) {
        int y = x^n;
        Min = min(Min, dp(x)+dp(y));
    }
    F[n] = common[n];
    if (Min < oo) F[n] = Min - F[n];
    //cerr << "dp(" << n << ") = " << F[n] << "\n";
    return F[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> s[i];
        for (int c=0; c<26; c++) cnt[i][c] = 0;
        for (int j=0; j<s[i].size(); j++) {
            int c = s[i][j] - 'a';
            cnt[i][c]++;
        }
    }
    //cerr << "Input successfully\n";
    for (int mask=1; mask<(1<<n); mask++) { //common
        common[mask] = 0;
        for (int c=0; c<26; c++) {
            int add = oo;
            for (int i=0; i<n; i++)
                if (((mask>>i)&1) > 0) add = min(add, cnt[i][c]);
            common[mask] += add;
        }
    }
    //cerr << "Pre-processing successfully\n";
    memset(F, -1, sizeof(F));
    cout << 1 + dp((1<<n)-1);
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<s[i].size(); j++) {
                       ~^~~~~~~~~~~~

• Subtask 1: 160 / 160