oj.uz

Submission #241457

# Submission time Handle Problem Language Result Execution time Memory
241457 2020-06-24T08:14:26 Z VEGAnn Vještica (COCI16_vjestica) C++14
160 / 160
 104 ms 1480 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 16;
const int M = 100100;
const int AL = 26;
const int PW = (1 << 16);
const int oo = 2e9;
string s;
int cnt[N][AL], f[PW], eco[PW], mn[AL], n;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s;

        for (int j = 0; j < sz(s); j++)
            cnt[i][s[j] - 'a']++;
    }

    for (int msk = 1; msk < (1 << n); msk++){
        fill(mn, mn + AL, oo);

        for (int i = 0; i < n; i++)
            if (msk & (1 << i)){
                for (int j = 0; j < 26; j++)
                    mn[j] = min(mn[j], cnt[i][j]);
            }

        for (int j = 0; j < 26; j++)
            eco[msk] += mn[j];
    }

    for (int msk = 1; msk < (1 << n); msk++)
        if (__builtin_popcount(msk) == 1)
            f[msk] = eco[msk];
        else {
            f[msk] = oo;

            for (int sub = ((msk - 1) & msk); sub > 0; sub = (sub - 1) & msk){
                f[msk] = min(f[msk], f[sub] + f[msk ^ sub] - eco[msk]);
            }
        }

    cout << 1 + f[(1 << n) - 1];

    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 98 ms 888 KB Output is correct
5 Correct 99 ms 888 KB Output is correct
6 Correct 102 ms 1144 KB Output is correct
7 Correct 104 ms 1480 KB Output is correct
8 Correct 100 ms 1400 KB Output is correct
9 Correct 104 ms 1404 KB Output is correct
10 Correct 100 ms 1400 KB Output is correct