oj.uz

Submission #126956

# Submission time Handle Problem Language Result Execution time Memory
126956 2019-07-08T16:59:17 Z stefdasca Vještica (COCI16_vjestica) C++14
160 / 160
 405 ms 1532 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 = i & (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
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 392 ms 1016 KB Output is correct
5 Correct 402 ms 1016 KB Output is correct
6 Correct 399 ms 1272 KB Output is correct
7 Correct 393 ms 1384 KB Output is correct
8 Correct 399 ms 1348 KB Output is correct
9 Correct 405 ms 1532 KB Output is correct
10 Correct 397 ms 1444 KB Output is correct