oj.uz

Submission #298988

# Submission time Handle Problem Language Result Execution time Memory
298988 2020-09-14T11:50:16 Z MladenP Vještica (COCI16_vjestica) C++17
160 / 160
 195 ms 1400 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define pll pair<lld,lld>
#define all(x) begin(x),end(x)
#define mid ((l+r)/2)
#define sz(x) int((x).size())
#define endl '\n'
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define INF 1000000000
#define pb push_back
using namespace std;
#define MAXN 20
int cnt[MAXN][30];
int dp[2000000], N, L[2000000];
int len(int mask) {
    if(L[mask] > 0) return L[mask];
    int c[30];
    for(int i = 0; i < 26; i++) c[i] = INF;
    for(int i = 0; i < N; i++) {
        if((1<<i)&mask) {
            for(int j = 0; j < 26; j++) c[j] = min(c[j], cnt[i][j]);
        }
    }
    for(int i = 0; i < 26; i++) L[mask] += c[i];
    return L[mask];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++) {
        string x; cin >> x;
        for(auto s : x) {
            cnt[i][s-'a']++;
        }
    }

    for(int mask = 1; mask < (1<<N); mask++) {
        if(__builtin_popcount(mask) == 1) {
            dp[mask] = len(mask);
            continue;
        }
        dp[mask] = INF;
        int submask = mask;
        submask = (submask-1)&mask;
        while(submask > 0) {
            dp[mask] = min(dp[mask], dp[submask]+dp[submask^mask]-len(mask));
            submask = (submask-1)&mask;
        }
    }
    int kraj = 0;
    for(int i = 0; i < N; i++) kraj |= (1<<i);
    cout << dp[kraj] +1;
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 184 ms 1000 KB Output is correct
5 Correct 195 ms 1024 KB Output is correct
6 Correct 185 ms 1144 KB Output is correct
7 Correct 187 ms 1396 KB Output is correct
8 Correct 189 ms 1400 KB Output is correct
9 Correct 185 ms 1008 KB Output is correct
10 Correct 189 ms 1012 KB Output is correct