Submission #252165

#	Time	Username	Problem	Language	Result	Execution time	Memory
252165		lookcook	Vještica (COCI16_vjestica)	C++17	0 / 160	2093 ms	896 KiB

vjestica

#include <bits/stdc++.h>

//#define int long long

using namespace std;

int recur(vector<vector<int>> s) {
    vector<vector<int>> vec(s.begin(), s.end());
    int res = 0;
    while (true) {
        vector<int> mins(26, 1e9);
        for (vector<int> v : vec) for (int j = 0; j < 26; j++) mins[j] = min(mins[j], v[j]);
        vector<vector<int>> copy = {};
        for (vector<int> v : vec) {
            for (int j = 0; j < 26; j++) v[j] -= mins[j];
            bool flag = false;
            for (int j = 0; j < 26; j++)
                if (v[j] > 0) {
                    flag = true;
                    break;
                }
            if (flag) copy.push_back(v);
        }
        for (int j = 0; j < 26; j++) res += mins[j];
        if (copy.empty()) return res;
        bool flag = false;
        for (int j = 0; j < 26; j++) if (mins[j] > 0) {
            flag = true;
            break;
        }
        if (!flag) break;
        vec = copy;
    }
    int others = 1e9;
    for (int i = 1; i < (1<<vec.size()); i++) {
        vector<vector<int>> s1;
        vector<vector<int>> s2;
        for (int j = 0; j < vec.size(); j++) {
            if ((1<<j)&i) s1.push_back(vec[j]);
            else s2.push_back(vec[j]);
        }
        if (s1.size() != 0 && s2.size() != 0) others = min(recur(s1)+recur(s2), others);
    }
    return res+others;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> s;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        vector<int> v(26, 0);
        for (int j = 0; j < str.size(); j++) v[str[j]-'a']++;
        s.push_back(v);
    }
    int res = recur(s);
    cout << res+1 << '\n';
}

Compilation message (stderr)

vjestica.cpp: In function 'int recur(std::vector<std::vector<int> >)':
vjestica.cpp:38:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vec.size(); j++) {
                         ~~^~~~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < str.size(); j++) v[str[j]-'a']++;
                         ~~^~~~~~~~~~~~

• Subtask 1: 0 / 160