oj.uz

Submission #126955

# Submission time Handle Problem Language Result Execution time Memory
126955 2019-07-08T16:57:29 Z stefdasca Vještica (COCI16_vjestica) C++14
0 / 160
 5 ms 1144 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;

int n, frq[30][30], dp[(1<<17)], viz[(1<<17)];
string s[20];
int prf(int msk)
{
    int mn[28];
    for(int i = 0; i <= 25; ++i)
        mn[i] = (1<<30);
    for(int i = 0; i < n; ++i)
    {
        if(msk & (1<<i))
            for(int j = 0; j <= 25; ++j)
                mn[j] = min(mn[j], frq[i][j]);
    }
    int ans = 0;
    for(int j = 0; j <= 25; ++j)
        ans += mn[j];
    return ans;
}
int solve(int i)
{
    if(viz[i])
        return dp[i];
    viz[i] = 1;
    int x = prf(i);
    vector<int>v;
    for(int j = 0; j < n; ++j)
        if(i & (1<<j))
            v.push_back(j);
    if(v.size() == 1)
    {
        dp[i] = x;
        return dp[i];
    }
    dp[i] = (1<<29);
    for(int j = i & (i-1); j; j = j & (j-1))
        dp[i] = min(dp[i], solve(j) + solve(i ^ j) - x);
    return dp[i];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> s[i];
        for(int j = 0; j < s[i].size(); ++j)
            frq[i][s[i][j] - 'a']++;
    }
    cout << solve((1<<n) - 1) + 1 << '\n';
    return 0;
}

Compilation message

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

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 2 ms 504 KB Output isn't correct
5 Incorrect 3 ms 632 KB Output isn't correct
6 Incorrect 4 ms 760 KB Output isn't correct
7 Incorrect 5 ms 1016 KB Output isn't correct
8 Incorrect 5 ms 1144 KB Output isn't correct
9 Incorrect 5 ms 1016 KB Output isn't correct
10 Incorrect 5 ms 1144 KB Output isn't correct