oj.uz

Submission #736188

# Submission time Handle Problem Language Result Execution time Memory
736188 2023-05-05T09:53:03 Z Nhoksocqt1 Vještica (COCI16_vjestica) C++17
160 / 160
 103 ms 1184 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 16;

int dp[1 << MAXN], cnt[MAXN + 4][30], tmp[30], numString;

void process() {
    cin >> numString;
    for (int i = 1; i <= numString; ++i) {
        string str;
        cin >> str;

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

    for (int mask = 1; mask < (1 << numString); ++mask) {
        for (int i = 0; i < 26; ++i)
            tmp[i] = 1e9;

        for (int i1 = mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1) + 1;
            for (int j = 0; j < 26; ++j)
                tmp[j] = min(tmp[j], cnt[i][j]);
        }

        int sum(0);
        for (int i = 0; i < 26; ++i)
            sum += tmp[i];

        if(__builtin_popcount(mask) == 1) {
            dp[mask] = sum;
            continue;
        }

        dp[mask] = 1e9+7;
        for (int maskx = (mask - 1) & mask; maskx > 0; maskx = (maskx - 1) & mask) {
            dp[mask] = min(dp[mask], dp[maskx] + dp[mask ^ maskx] - sum);
        }
    }

    cout << 1 + dp[(1 << numString) - 1];
}

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

    process();
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 95 ms 608 KB Output is correct
5 Correct 97 ms 716 KB Output is correct
6 Correct 92 ms 828 KB Output is correct
7 Correct 92 ms 1060 KB Output is correct
8 Correct 103 ms 1184 KB Output is correct
9 Correct 88 ms 1044 KB Output is correct
10 Correct 93 ms 1080 KB Output is correct