oj.uz

Submission #521057

# Submission time Handle Problem Language Result Execution time Memory
521057 2022-01-31T16:36:20 Z Vladth11 Vještica (COCI16_vjestica) C++14
160 / 160
 110 ms 708 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const int NMAX = 16;
const int VMAX = 21;
const int INF = (1LL << 60);
const int MOD = 1000000007;
const int BLOCK = 318;
const int base = 31;
const int nr_of_bits = 21;

int dp[(1 << NMAX)];
int cnt[NMAX][26];

int lcp(int a){
    int sol = 0;
    for(int j = 0; j < 26; j++){
        int minim = 2e9;
        for(int i = 0; i < NMAX; i++){
            if((a & (1 << i)))
                minim = min(minim, cnt[i][j]);
        }
        sol += minim;
    }
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < (1 << n); i++)
        dp[i] = 1e9;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(auto x : s) {
            cnt[i][x - 'a']++;
        }
        dp[(1 << i)] = s.size();
    }
    for(int mask = 0; mask < (1 << n); mask++) {
        int p = lcp(mask);
        for(int submask = (mask - 1) & mask; submask > 0; submask = ((submask - 1) & mask)) {
            dp[mask] = min(dp[mask], dp[submask] + dp[(submask ^ mask)] - p);
        }
    }
    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

Compilation message

vjestica.cpp:12:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
   12 | const int INF = (1LL << 60);
      |                 ~~~~~^~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 101 ms 564 KB Output is correct
5 Correct 102 ms 708 KB Output is correct
6 Correct 103 ms 588 KB Output is correct
7 Correct 105 ms 684 KB Output is correct
8 Correct 101 ms 668 KB Output is correct
9 Correct 110 ms 668 KB Output is correct
10 Correct 105 ms 660 KB Output is correct