oj.uz

Submission #248376

# Submission time Handle Problem Language Result Execution time Memory
248376 2020-07-12T10:07:51 Z Vladikus004 Vještica (COCI16_vjestica) C++14
160 / 160
 304 ms 1656 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 16;
int n, cnt[N][26], dp[(1<<16) + 3];
string s[N];

int get_pref(int mask){
    int mn[26];
    fill(mn, mn + 26, inf);
    for (int i = 0; i < n; i++){
        if (!((1<<i) & mask)) continue;
        for (int j = 0; j < 26; j++)
            mn[j] = min(mn[j], cnt[i][j]);
    }
    int sum = 0;
    for (int i = 0; i < 26; i++)
        sum += mn[i];
    return sum;
}

int get_ans(int mask){
    if (dp[mask] != -1) return dp[mask];
    int pref = get_pref(mask);
    if (__builtin_popcount(mask) == 1) return pref;
    dp[mask] = inf;
    for (int i = mask & (mask - 1); i > 0; i = (i - 1) & mask)
        dp[mask] = min(dp[mask], get_ans(i) + get_ans(mask^i) - pref);
    return dp[mask];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s[i];
        for (int j = 0; j < s[i].size(); j++)
            cnt[i][s[i][j] - 'a']++;
    }
    cout << get_ans((1<<n)-1) + 1;
}

Compilation message

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

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 291 ms 760 KB Output is correct
5 Correct 294 ms 800 KB Output is correct
6 Correct 294 ms 1272 KB Output is correct
7 Correct 304 ms 1512 KB Output is correct
8 Correct 293 ms 1536 KB Output is correct
9 Correct 293 ms 1656 KB Output is correct
10 Correct 289 ms 1536 KB Output is correct