oj.uz

Submission #712406

# Submission time Handle Problem Language Result Execution time Memory
712406 2023-03-18T18:26:55 Z Ahmed57 Vještica (COCI16_vjestica) C++14
160 / 160
 173 ms 1456 KB 
#include<bits/stdc++.h>
using namespace std;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
long long dp[(1<<16)];
long long c[16][26] = {0};
long  long com[(1<<16)];
long long solve(int mask){
    if(dp[mask]!=-1)return dp[mask];
    if(__builtin_popcount(mask)==1)return 0;
    long long ans = 1e18;
    for(int s = mask&(mask-1);s;s=(mask&(s-1))){
        ans = min(ans,solve(s)+solve(mask^s)+((-2)*com[mask]+com[s]+com[(mask^s)]));
    }
    return dp[mask] = ans;
}
signed 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 j:s){
            c[i][j-'a']++;
        }
    }
    memset(dp,-1,sizeof dp);
    for(int mask = 0;mask<(1<<n);mask++){
        long long ch[26] = {0};
        for(int j = 0;j<26;j++)ch[j] = 1e9;
        for(int j = 0;j<n;j++){
            if(mask&(1<<j)){
            for(int k = 0;k<26;k++)ch[k]= min(ch[k],c[j][k]);
            }
        }
        for(int j = 0;j<26;j++){
            com[mask]+=ch[j];
        }
    }
    cout<<solve((1<<n)-1)+1+com[(1<<n)-1]<<endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 126 ms 1344 KB Output is correct
5 Correct 132 ms 1360 KB Output is correct
6 Correct 173 ms 1424 KB Output is correct
7 Correct 124 ms 1456 KB Output is correct
8 Correct 131 ms 1444 KB Output is correct
9 Correct 126 ms 1444 KB Output is correct
10 Correct 140 ms 1452 KB Output is correct