oj.uz

Submission #169200

# Submission time Handle Problem Language Result Execution time Memory
169200 2019-12-19T02:22:36 Z _qVp_ Vještica (COCI16_vjestica) C++14
160 / 160
 1995 ms 1784 KB 
#include<bits/stdc++.h>
using namespace std;

const int mN = 16;
const int mB = (1<<mN);
const int oo = 1e9;
string s[mN];
int cnt[mN][26];
int common[mB];
int F[mB];

int dp(int n) {
    if (n == 0) return 0;
    if (F[n] > -1) return F[n];
    int Min = oo;
    for (int x=1; x<n; x++) if ((x|n) == n) {
        int y = x^n;
        Min = min(Min, dp(x)+dp(y));
    }
    F[n] = common[n];
    if (Min < oo) F[n] = Min - F[n];
    //cerr << "dp(" << n << ") = " << F[n] << "\n";
    return F[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> s[i];
        for (int c=0; c<26; c++) cnt[i][c] = 0;
        for (int j=0; j<s[i].size(); j++) {
            int c = s[i][j] - 'a';
            cnt[i][c]++;
        }
    }
    //cerr << "Input successfully\n";
    for (int mask=1; mask<(1<<n); mask++) { //common
        common[mask] = 0;
        for (int c=0; c<26; c++) {
            int add = oo;
            for (int i=0; i<n; i++)
                if (((mask>>i)&1) > 0) add = min(add, cnt[i][c]);
            common[mask] += add;
        }
    }
    //cerr << "Pre-processing successfully\n";
    memset(F, -1, sizeof(F));
    cout << 1 + dp((1<<n)-1);
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:36:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<s[i].size(); j++) {
                       ~^~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 1989 ms 1016 KB Output is correct
5 Correct 1988 ms 988 KB Output is correct
6 Correct 1991 ms 1216 KB Output is correct
7 Correct 1992 ms 1384 KB Output is correct
8 Correct 1995 ms 1440 KB Output is correct
9 Correct 1987 ms 1784 KB Output is correct
10 Correct 1988 ms 1400 KB Output is correct