oj.uz

Submission #521056

# Submission time Handle Problem Language Result Execution time Memory
521056 2022-01-31T16:29:18 Z Vladth11 Vještica (COCI16_vjestica) C++14
48 / 160
 2000 ms 716 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 b){
    int sol = 0;
    for(int j = 0; j < 26; j++){
        int minim = 2e9;
        for(int i = 0; i < NMAX; i++){
            if((a & (1 << i)) || (b & (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++) {
        for(int submask = (mask - 1) & mask; submask > 0; submask = ((submask - 1) & mask)) {
            dp[mask] = min(dp[mask], dp[submask] + dp[(submask ^ mask)] - lcp(submask, (mask ^ submask)));
        }
    }
    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
48.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 328 KB Output is correct
2 Correct 23 ms 204 KB Output is correct
3 Correct 21 ms 204 KB Output is correct
4 Execution timed out 2082 ms 588 KB Time limit exceeded
5 Execution timed out 2096 ms 588 KB Time limit exceeded
6 Execution timed out 2073 ms 716 KB Time limit exceeded
7 Execution timed out 2073 ms 716 KB Time limit exceeded
8 Execution timed out 2079 ms 716 KB Time limit exceeded
9 Execution timed out 2088 ms 716 KB Time limit exceeded
10 Execution timed out 2069 ms 716 KB Time limit exceeded