oj.uz

Submission #521053

# Submission time Handle Problem Language Result Execution time Memory
521053 2022-01-31T16:20:05 Z Vladth11 Vještica (COCI16_vjestica) C++14
0 / 160
 2000 ms 1096 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 solve(int mask) {
    vector <int> v;
    for(int i = 0; i < NMAX; i++) {
        if(mask & (1 << i))
            v.push_back(i);
    }
    if(v.size() == 1) {
        int c = 0;
        for(int j = 0; j < 26; j++) {
            c += cnt[v.back()][j];
            //debug(cnt[v.back()][j]);
        }
        return dp[mask] = c;
    }
    int cate = 0;
    vector <int> copie;
    for(int j = 0; j < 26; j++) {
        int minim = 2e9;
        for(auto x : v) {
            minim = min(minim, cnt[x][j]);
        }
        cate += minim;
        for(auto x : v) {
            cnt[x][j] -= minim;
        }
        copie.push_back(minim);
    }
    int minim = 2e9;
    for(int submask = (mask - 1) & mask; submask > 0; submask = ((submask - 1) & mask)) {
        minim = min(minim, cate + solve(submask) + solve(submask ^ mask));
    }
    for(int j = 0; j < 26; j++) {
        for(auto x : v) {
            cnt[x][j] += copie[j];
        }
    }
    return dp[mask] = minim;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(auto x : s){
            cnt[i][x - 'a']++;
        }
    }
    for(int i = 0; i < (1 << n); i++)
        dp[i] = -1;
    cout << solve((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
0 / 160.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 324 KB Time limit exceeded
2 Execution timed out 2071 ms 208 KB Time limit exceeded
3 Execution timed out 2060 ms 336 KB Time limit exceeded
4 Execution timed out 2072 ms 592 KB Time limit exceeded
5 Execution timed out 2057 ms 592 KB Time limit exceeded
6 Execution timed out 2025 ms 852 KB Time limit exceeded
7 Execution timed out 2073 ms 972 KB Time limit exceeded
8 Execution timed out 2023 ms 1096 KB Time limit exceeded
9 Execution timed out 2009 ms 964 KB Time limit exceeded
10 Execution timed out 2070 ms 972 KB Time limit exceeded