Submission #210623

#TimeUsernameProblemLanguageResultExecution timeMemory
210623ZwariowanyMarcinVještica (COCI16_vjestica)C++14
160 / 160
1406 ms7288 KiB
#include <bits/stdc++.h> #define LL long long #define LD long double #define pb push_back #define mp make_pair #define ss(x) (int) x.size() #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl #define rep2(i, j, n) for (LL i = j; i <= n; ++i) #define rep(i, j, n) for (int i = j; i <= n; ++i) #define per(i, j, n) for (int i = n; j <= i; --i) #define boost cin.tie(0);ios_base::sync_with_stdio(0); #define all(x) x.begin(), x.end() #define bignum vector <int> using namespace std; const int N = 1e6 + 10101; const int LOG = 16; int n; char s[N]; int a[20][26]; int cnt[1 << LOG][26]; int dp[1 << LOG]; int main() { scanf ("%d", &n); rep(i, 0, n - 1) { scanf ("%s", s + 1); int len = strlen(s + 1); rep(j, 1, len) a[i][s[j] - 'a']++; } rep(mask, 1, (1 << n) - 1) { rep(c, 0, 25) { int y = 1e9; rep(k, 0, n - 1) if (((mask >> k) & 1)) y = min(y, a[k][c]); cnt[mask][c] = y; } } rep(mask, 1, (1 << n) - 1) { if (__builtin_popcount(mask) == 1) { dp[mask] = 0; continue; } dp[mask] = 1e9; int sub = ((mask - 1) & mask); while (sub != 0) { int x = sub; int y = (mask ^ x); int z = dp[x] + dp[y]; rep(c, 0, 25) z += (cnt[x][c] + cnt[y][c] - cnt[mask][c] - cnt[mask][c]); assert(0 <= z); //if (mask == ((1 << n) - 1)) { // cat(z); // cat(dp[x] + dp[y]); // cat(x); // cat(y); //} dp[mask] = min(dp[mask], z); sub = ((sub - 1) & mask); } } int res = dp[(1 << n) - 1]; rep(c, 0, 25) res += cnt[(1 << n) - 1][c]; printf ("%d\n", res + 1); return 0; }

Compilation message (stderr)

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