Submission #249663

#TimeUsernameProblemLanguageResultExecution timeMemory
249663MercenaryVještica (COCI16_vjestica)C++14
48 / 160
2090 ms1152 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 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 < n ; ++i)dp[1 << i] = 0; for(int i = 0 ; i < (1 << n) ; ++i){ int tmp = get(i); for(int j = (i - 1) & i ; j > 0 ; j = ((j - 1) & i)){ dp[i] = min(dp[i] , dp[j] + dp[i ^ j] + get(j) + get(i ^ j) - 2 * get(i)); } } cout << 1 + get((1 << n) - 1) + dp[(1 << n) - 1]; }

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:50:13: warning: unused variable 'tmp' [-Wunused-variable]
         int tmp = get(i);
             ^~~
vjestica.cpp:39: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:40: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...