oj.uz

Submission #167650

# Submission time Handle Problem Language Result Execution time Memory
167650 2019-12-09T08:31:36 Z Flying_dragon_02 Vještica (COCI16_vjestica) C++14
0 / 160
 37 ms 1144 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], lmao[17][17], total, dp[( 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 ) );
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        t[i - 1] = s;
        for(int j = 0; j < (int)( s.length() ); j++) {
            int c = (int)( s[j] - 'a' );
            cnt[i][c]++;
        }
        total += (int)( s.length() );
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int sum = 0;
            for(int k = 0; k <= 25; k++)
                sum += min( cnt[i][k], cnt[j][k] );
            lmao[i - 1][j - 1] = lmao[j - 1][i - 1] = sum;
        }
    }
    for(int mask = 0; mask < (1 << n); mask++)
        dp[ mask ] = inf;
    for(int i = 0; i < n; i++)
        dp[ ( 1 << i ) ] = (int)( t[i].length() );
    for(int mask = 0; mask < (1 << n); mask++) {
        if( dp[mask] == inf ) continue;
        for(int bt1 = 0; bt1 < n; bt1++) {
            if( !checkBit( mask, bt1 ) ) continue;
            for(int bt2 = 0; bt2 < n; bt2++) {
                if( checkBit( mask, bt2 ) ) continue;
                dp[ changeBit( mask, bt2 ) ] = min( dp[ changeBit( mask, bt2 ) ], dp[ mask ] + (int)( t[bt2].length() ) - lmao[bt1][bt2] );
            }
        }
    }
    cout << dp[ (1 << n) - 1 ] + 1;
}

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Incorrect 2 ms 380 KB Output isn't correct
4 Incorrect 33 ms 632 KB Output isn't correct
5 Incorrect 34 ms 744 KB Output isn't correct
6 Incorrect 35 ms 888 KB Output isn't correct
7 Incorrect 36 ms 1096 KB Output isn't correct
8 Incorrect 37 ms 1144 KB Output isn't correct
9 Incorrect 36 ms 1144 KB Output isn't correct
10 Incorrect 36 ms 1144 KB Output isn't correct