oj.uz

Submission #304959

# Submission time Handle Problem Language Result Execution time Memory
304959 2020-09-22T09:32:12 Z BeanZ Vještica (COCI16_vjestica) C++14
160 / 160
 1259 ms 1272 KB 
// 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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 1237 ms 760 KB Output is correct
5 Correct 1245 ms 640 KB Output is correct
6 Correct 1242 ms 896 KB Output is correct
7 Correct 1247 ms 1140 KB Output is correct
8 Correct 1246 ms 1272 KB Output is correct
9 Correct 1259 ms 1268 KB Output is correct
10 Correct 1254 ms 1152 KB Output is correct