Submission #304959

#	Time	Username	Problem	Language	Result	Execution time	Memory
304959		BeanZ	Vještica (COCI16_vjestica)	C++14	160 / 160	1259 ms	1272 KiB

vjestica

// I_Love_LPL
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define endl '\n'
const int N = 1e5 + 5;
ll cnt[20][26], dp[(1 << 16) + 1];
ll n;
ll cal(ll mask){
        ll ans = 0;
        for (int j = 0; j < 26; j++){
                ll res = 1e9;
                for (int i = 0; i < n; i++){
                        if (mask & (1 << i)){
                                res = min(res, cnt[i][j]);
                        }
                }
                ans = ans + res;
        }
        return ans;
}
ll DP(ll mask){
        if (__builtin_popcount(mask) == 1) return cal(mask);
        if (dp[mask] != -1) return dp[mask];
        ll prev = cal(mask);
        dp[mask] = 1e9;
        for (int i = (mask - 1) & mask; i; i = (i - 1) & mask){
                dp[mask] = min(dp[mask], DP(i) + DP(mask ^ i) - prev);
        }
        return dp[mask];
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.inp", "r")){
                freopen("test.inp", "r", stdin);
                freopen("test.out", "w", stdout);
        }
        cin >> n;
        for (int i = 0; i < n; i++){
                string s;
                cin >> s;
                for (int j = 0; j < s.length(); j++){
                        cnt[i][s[j] - 'a']++;
                }
        }
        memset(dp, -1, sizeof(dp));
        cout << DP((1 << n) - 1) + 1;
}
/*
*/

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:45:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 for (int j = 0; j < s.length(); j++){
      |                                 ~~^~~~~~~~~~~~
vjestica.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   38 |                 freopen("test.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
vjestica.cpp:39:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   39 |                 freopen("test.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160