oj.uz

Submission #816947

# Submission time Handle Problem Language Result Execution time Memory
816947 2023-08-09T07:40:19 Z Theo830 Vještica (COCI16_vjestica) C++17
160 / 160
 150 ms 1888 KB 
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define pb push_back
#define F first
#define S second
const ll INF = 1e9+7;
ll dp[1<<16];
ll exo[1<<16];
ll siz[16][26];
ll n;
ll koina(ll mask){
    if(exo[mask] != -1){
        return exo[mask];
    }
    ll mini[26];
    f(j,0,26){
        mini[j] = INF;
    }
    f(i,0,n){
        if((mask & (1<<i))){
            f(j,0,26){
                mini[j] = min(mini[j],siz[i][j]);
            }
        }
    }
    ll ans = 0;
    f(j,0,26){
        ans += mini[j];
    }
    return exo[mask] = ans;
}
ll solve(ll mask){
    if(dp[mask] != -1){
        return dp[mask];
    }
    ll res = INF;
    bool ok = 0;
    for(ll j = (mask - 1) & mask;j > 0;j = (j - 1) & mask){
        ok = 1;
        res = min(res,solve(j) + solve(mask ^ j) + koina(j) + koina(mask ^ j));
    }
    if(!ok){
        res = 0;
    }
    else{
        res -= 2 * koina(mask);
    }
    return dp[mask] = res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof dp);
    memset(exo,-1,sizeof exo);
    cin>>n;
    f(i,0,n){
        string s;
        cin>>s;
        f(j,0,26){
            siz[i][j] = 0;
        }
        for(auto x:s){
            siz[i][x - 'a']++;
        }
    }
    cout<<1 + solve((1<<n) - 1) + koina((1<<n) - 1)<<"\n";
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 138 ms 1364 KB Output is correct
5 Correct 120 ms 1444 KB Output is correct
6 Correct 121 ms 1644 KB Output is correct
7 Correct 150 ms 1836 KB Output is correct
8 Correct 115 ms 1888 KB Output is correct
9 Correct 137 ms 1848 KB Output is correct
10 Correct 114 ms 1756 KB Output is correct