Submission #521053

#	Time	Username	Problem	Language	Result	Execution time	Memory
521053		Vladth11	Vještica (COCI16_vjestica)	C++14	0 / 160	2073 ms	1096 KiB

vjestica

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const int NMAX = 16;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 21;

int dp[(1 << NMAX)];
int cnt[NMAX][26];

int solve(int mask) {
    vector <int> v;
    for(int i = 0; i < NMAX; i++) {
        if(mask & (1 << i))
            v.push_back(i);
    }
    if(v.size() == 1) {
        int c = 0;
        for(int j = 0; j < 26; j++) {
            c += cnt[v.back()][j];
            //debug(cnt[v.back()][j]);
        }
        return dp[mask] = c;
    }
    int cate = 0;
    vector <int> copie;
    for(int j = 0; j < 26; j++) {
        int minim = 2e9;
        for(auto x : v) {
            minim = min(minim, cnt[x][j]);
        }
        cate += minim;
        for(auto x : v) {
            cnt[x][j] -= minim;
        }
        copie.push_back(minim);
    }
    int minim = 2e9;
    for(int submask = (mask - 1) & mask; submask > 0; submask = ((submask - 1) & mask)) {
        minim = min(minim, cate + solve(submask) + solve(submask ^ mask));
    }
    for(int j = 0; j < 26; j++) {
        for(auto x : v) {
            cnt[x][j] += copie[j];
        }
    }
    return dp[mask] = minim;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(auto x : s){
            cnt[i][x - 'a']++;
        }
    }
    for(int i = 0; i < (1 << n); i++)
        dp[i] = -1;
    cout << solve((1 << n) - 1) + 1;
    return 0;
}

Compilation message (stderr)

vjestica.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   12 | const int INF = (1LL << 60);
      |                 ~~~~~^~~~~~

• Subtask 1: 0 / 160