oj.uz

Submission #252165

# Submission time Handle Problem Language Result Execution time Memory
252165 2020-07-24T13:11:55 Z lookcook Vještica (COCI16_vjestica) C++17
0 / 160
 2000 ms 896 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 384 KB Time limit exceeded
2 Execution timed out 2078 ms 384 KB Time limit exceeded
3 Execution timed out 2077 ms 384 KB Time limit exceeded
4 Execution timed out 2093 ms 384 KB Time limit exceeded
5 Execution timed out 2090 ms 512 KB Time limit exceeded
6 Execution timed out 2090 ms 640 KB Time limit exceeded
7 Execution timed out 2084 ms 892 KB Time limit exceeded
8 Execution timed out 2086 ms 896 KB Time limit exceeded
9 Execution timed out 2055 ms 888 KB Time limit exceeded
10 Execution timed out 2086 ms 896 KB Time limit exceeded