oj.uz

Submission #117501

# Submission time Handle Problem Language Result Execution time Memory
117501 2019-06-16T09:58:24 Z FutymyClone Vještica (COCI16_vjestica) C++14
0 / 160
 104 ms 1588 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 16;

int n, cnt[N][26], temp[26], valmask[1 << N], dp[1 << N], sum[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.length(); j++) cnt[i][s[j] - 'a']++;
        sum[i] = s.length();
    }

    for (int mask = 0; mask < (1 << n); mask++) {
        memset(temp, 0x3f, sizeof(temp));
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < 26; j++) if (cnt[i][j]) temp[j] = min(temp[j], cnt[i][j]);
            }
        }

        for (int i = 0; i < 26; i++) if (temp[i] < 1e9) valmask[mask] += temp[i];
        int res = valmask[mask];
        for (int i = 0; i < n; i++) if (mask & (1 << i)) valmask[mask] += max(0, sum[i] - res);
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            dp[mask] = min(dp[mask], dp[mask ^ submask] + valmask[submask]);
        }
    }

    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:15:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.length(); j++) cnt[i][s[j] - 'a']++;
                         ~~^~~~~~~~~~~~

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Incorrect 2 ms 640 KB Output isn't correct
3 Incorrect 0 ms 640 KB Output isn't correct
4 Incorrect 104 ms 892 KB Output isn't correct
5 Incorrect 103 ms 1016 KB Output isn't correct
6 Incorrect 97 ms 1144 KB Output isn't correct
7 Incorrect 101 ms 1408 KB Output isn't correct
8 Incorrect 97 ms 1588 KB Output isn't correct
9 Incorrect 98 ms 1320 KB Output isn't correct
10 Incorrect 98 ms 1408 KB Output isn't correct