Submission #165680

#	Time	Username	Problem	Language	Result	Execution time	Memory
165680		egekabas	Vještica (COCI16_vjestica)	C++14	0 / 160	755 ms	2040 KiB

vjestica

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n;
string s[30];
ll scnt[30][30];
ll bcnt[1<<18];
ll dp[1<<18];

ll func(ll bit){
    if(dp[bit] != -1)
        return dp[bit];
    ll pre = 0;
    dp[bit] = 0;
    ll use[30][30];
    ll left[30];
    for(ll i = 0; i < n; ++i){
        left[i] = 0;
        for(ll j = 0; j <= 'z'-'a'; ++j){
            use[i][j] = scnt[i][j];
            left[i] += use[i][j];
        }
    }
    ll check = 1;
    while(check){
        check = 0;
        for(ll i = 0; i <= 'z'-'a'; ++i){
            ll cur = 1e18;
            for(ll j = 0; j < n; ++j)
                if((bit&(1<<j)) != 0 && left[j] != 0)
                    cur = min(cur, use[j][i]);
            if(cur == 1e18)
                goto HERE;
            pre += cur;
            for(ll j = 0; j < n; ++j)
                if((bit&(1<<j)) != 0 && left[j] != 0){
                    use[j][i] -= cur;
                    left[j] -= cur;
                    if(left[j] == 0)
                        check = 1;
                }
        }
    }
    HERE:;
    dp[bit] = pre;
    //cout << bit << " " << pre << "\n";
    for(ll j = 0; j < n; ++j)
        if((bit&(1<<j)) != 0)
            dp[bit] += max((ll)0, (ll)s[j].size()-pre);
    for(ll bit2 = ((bit-1)&bit); bit2 > 0; bit2 = ((bit2-1)&bit))
        dp[bit] = min(dp[bit], func(bit2)+func(bit-bit2));
    return dp[bit];
}
ll check(string s1, string s2){
    for(int i = 0; i < min(s1.size(), s2.size()); ++i)
        if(s1[i] != s2[i])
            return 0;
    if(s1.size() > s2.size())
        return 1;
    return 2;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n;
    for(ll i = 0; i < n; ++i){
        cin >> s[i];
        for(auto u : s[i])
            scnt[i][u-'a']++;
    }
    for(ll bit = 0; bit < (1<<n); ++bit){
        dp[bit]= -1;
    }
    cout << 1+func((1<<n)-1) << "\n";
}

Compilation message (stderr)

vjestica.cpp: In function 'll check(std::__cxx11::string, std::__cxx11::string)':
vjestica.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < min(s1.size(), s2.size()); ++i)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 160