oj.uz

Submission #167656

# Submission time Handle Problem Language Result Execution time Memory
167656 2019-12-09T09:21:13 Z Flying_dragon_02 Vještica (COCI16_vjestica) C++14
160 / 160
 192 ms 1784 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair< int, int > ii;

const int inf = 1e8;

int n, cnt[17][27], dp[ ( 1 << 16 ) ], f[ ( 1 << 16 ) ];

string t[17];

bool checkBit(int mask, int bit) {
    if( ( mask & ( 1 << bit ) ))
        return 1;
    else
        return 0;
}

int changeBit(int mask, int bit) {
    return ( mask ^ ( 1 << bit ) );
}

#define bp __builtin_popcount

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        t[i] = s;
        for(int j = 0; j < (int)( s.length() ); j++) {
            int c = (int)( s[j] - 'a' );
            cnt[i][c]++;
        }
    }
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int c = 0; c < 26; c++) {
            int mn = inf;
            for(int bt = 0; bt < n; bt++) {
                if( checkBit( mask, bt ) )
                    mn = min( mn, cnt[bt][c] );
            }
            f[ mask ] += mn;
        }
    }
    dp[0] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        int total = 0, cnt1 = 0;
        for(int bt = 0; bt < n; bt++) {
            if( checkBit( mask, bt ) )
                total += (int)( t[bt].length() ), cnt1++;
        }
        cnt1 -= 1;
        total -= cnt1 * f[ mask ];
        dp[ mask ] = total;
        //cout << dp[mask] << " " << total << "\n";
        for(int submask = mask; submask > 0; submask = (submask - 1) & mask ) {
            if( submask == mask ) continue;
            dp[ mask ] = min( dp[mask], dp[ submask ] + dp[ mask ^ submask ] - f[ mask ] );
            //cout << mask << " " << submask << "\n";
        }
    }
    cout << dp[ (1 << n) - 1 ] + 1;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 188 ms 948 KB Output is correct
5 Correct 189 ms 1292 KB Output is correct
6 Correct 191 ms 1744 KB Output is correct
7 Correct 190 ms 1656 KB Output is correct
8 Correct 190 ms 1784 KB Output is correct
9 Correct 190 ms 1784 KB Output is correct
10 Correct 192 ms 1784 KB Output is correct