oj.uz

Submission #126954

# Submission time Handle Problem Language Result Execution time Memory
126954 2019-07-08T16:54:00 Z stefdasca Vještica (COCI16_vjestica) C++14
0 / 160
 2000 ms 9716 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 = 1; j + 1 < (1<<v.size()); ++j)
    {
        int xx = 0;
        for(int q = 0; q < v.size(); ++q)
            if(j & (1<<q))
                xx += (1<<q);
        dp[i] = min(dp[i], solve(xx) + solve(i ^ xx) - 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 solve(int)':
vjestica.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int q = 0; q < v.size(); ++q)
                        ~~^~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:59: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 5 ms 632 KB Output isn't correct
2 Incorrect 5 ms 632 KB Output isn't correct
3 Incorrect 5 ms 504 KB Output isn't correct
4 Execution timed out 2058 ms 8668 KB Time limit exceeded
5 Execution timed out 2056 ms 8888 KB Time limit exceeded
6 Execution timed out 2061 ms 9128 KB Time limit exceeded
7 Execution timed out 2045 ms 9464 KB Time limit exceeded
8 Execution timed out 2045 ms 9716 KB Time limit exceeded
9 Execution timed out 2033 ms 9464 KB Time limit exceeded
10 Execution timed out 2057 ms 9468 KB Time limit exceeded