Submission #249665

#TimeUsernameProblemLanguageResultExecution timeMemory
249665MercenaryVještica (COCI16_vjestica)C++14
160 / 160
131 ms1016 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int maxn = 5e5 + 5; const int logn = log2(maxn) + 1; int a[16][26]; int n; int dp[1 << 16]; int tmp[1 << 16]; int get(int s){ if(s == 0)return 0; int res = 0; for(int i = 0 ; i < 26 ; ++i){ int tmp = 1e6; for(int j = 0 ; j < n ; ++j){ if(s & (1 << j))tmp = min(tmp , a[j][i]); } res += tmp; } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } cin >> n; for(int i = 0 ; i < n ; ++i){ string s;cin >> s; for(auto & c : s)a[i][c - 'a']++; } memset(dp,123,sizeof dp); for(int i = 0 ; i < (1 << n) ; ++i)tmp[i] = get(i); for(int i = 0 ; i < n ; ++i)dp[1 << i] = 0; for(int i = 0 ; i < (1 << n) ; ++i){ for(int j = (i - 1) & i ; j > 0 ; j = ((j - 1) & i)){ dp[i] = min(dp[i] , dp[j] + dp[i ^ j] + tmp[j] + tmp[i ^ j] - 2 * tmp[i]); } } cout << 1 + get((1 << n) - 1) + dp[(1 << n) - 1]; }

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
vjestica.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...