oj.uz

Submission #225785

# Submission time Handle Problem Language Result Execution time Memory
225785 2020-04-21T15:19:59 Z osaaateiasavtnl Vještica (COCI16_vjestica) C++14
160 / 160
 117 ms 1916 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 17, INF = 1e9 + 7;
int dp[1 << N];
string a[N];
int cnt[N][26];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    /*
    for (int s=m; s; s=(s-1)&m)
    */
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (char c : a[i])
            ++cnt[i][c - 'a'];
    }
    for (int mask = 1; mask < (1 << n); ++mask) {
        int lcp = 0;
        for (int c = 0; c < 26; ++c) {
            int add = INF;
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    add = min(add, cnt[i][c]);
                }   
            }   
            lcp += add;
        }   

        if (bp(mask) == 1) {
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    dp[mask] = a[i].size();
                    break;
                }   
            }   
        }   
        else {
            dp[mask] = INF;
            for (int s=mask; s; s=(s-1)&mask) {
                //cout << mask << ' ' << s << ' ' << lcp << endl;
                dp[mask] = min(dp[mask], dp[s] + dp[mask ^ s] - lcp);
            }
        }      
    }   
    int all = (1 << n) - 1;
    cout << dp[all] + 1 << endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 109 ms 888 KB Output is correct
5 Correct 114 ms 1016 KB Output is correct
6 Correct 117 ms 1400 KB Output is correct
7 Correct 113 ms 1780 KB Output is correct
8 Correct 113 ms 1656 KB Output is correct
9 Correct 116 ms 1916 KB Output is correct
10 Correct 114 ms 1756 KB Output is correct