oj.uz

Submission #164359

# Submission time Handle Problem Language Result Execution time Memory
164359 2019-11-19T14:40:01 Z _qVp_ Vještica (COCI16_vjestica) C++14
160 / 160
 319 ms 1524 KB 
#include <bits/stdc++.h>

using namespace std;

const int md = (1 << 16) + 10;
const int oo = 1e9;

int memo[md], cnt[30][30], common[md], d[30];
int n;

int getbit(int x, int i) {
    return ((x >> i) & 1);
}

int dp(int mask) {
    if (memo[mask] != -1)
        return memo[mask];
    if (__builtin_popcount(mask) == 1)
        return memo[mask] = common[mask];
    int res = oo;
    for(int s = mask & (mask - 1); s; s = (s - 1) & mask) 
        res = min(res, dp(s) + dp(mask ^ s) - common[mask]);
    return memo[mask] = res;
}

int main() {
    //freopen("test.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++)
            cnt[i][s[j] - 'a']++;
    }

    for(int mask = 0; mask < (1 << n); mask++) {
        for(int i = 0; i < 26; i++)
            d[i] = oo;
        for(int i = 0; i < n; i++)
            if (getbit(mask, i)) {
                for(int j = 0; j < 26; j++)
                    d[j] = min(d[j], cnt[i][j]);
            }
        for(int i = 0; i < 26; i++)
            common[mask] += d[i];
    }

    memset(memo, -1, sizeof memo);
    //return 0;
    cout << dp((1 << n) - 1) + 1;
    return 0;
}

Compilation message

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

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 313 ms 888 KB Output is correct
5 Correct 312 ms 1016 KB Output is correct
6 Correct 315 ms 1148 KB Output is correct
7 Correct 318 ms 1524 KB Output is correct
8 Correct 319 ms 1468 KB Output is correct
9 Correct 315 ms 1524 KB Output is correct
10 Correct 313 ms 1400 KB Output is correct