Submission #201197

#TimeUsernameProblemLanguageResultExecution timeMemory
201197SamAndVještica (COCI16_vjestica)C++17
160 / 160
132 ms892 KiB
#include <bits/stdc++.h> using namespace std; const int N = 18, M = 1000006; int n; char s[M]; int a[N][26]; int b[(1 << N)]; int dp[(1 << N)]; int main() { //freopen("input.txt", "r", stdin); scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf(" %s", s); int m = strlen(s); for (int j = 0; j < m; ++j) a[i][s[j] - 'a']++; } for (int x = 1; x < (1 << n); ++x) { for (int j = 0; j < 26; ++j) { int minu = M; for (int i = 0; i < n; ++i) { if ((x & (1 << i))) { minu = min(minu, a[i][j]); } } b[x] += minu; } } for (int x = 1; x < (1 << n); ++x) { dp[x] = M; int q = 0; for (int i = 0; i < n; ++i) { if ((x & (1 << i))) { ++q; } } if (q == 1) { dp[x] = b[x]; continue; } for (int y = (x - 1) & x; y; y = (y - 1) & x) { int z = (x ^ y); dp[x] = min(dp[x], b[x] + dp[z] + dp[y] - b[x] - b[x]); } } printf("%d\n", dp[(1 << n) - 1] + 1); return 0; }

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
vjestica.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", s);
         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...