oj.uz

답안 #210622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210622 2020-03-17T22:54:29 Z ZwariowanyMarcin Vještica (COCI16_vjestica) C++14
32 / 160
 1392 ms 7800 KB 
#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 = n + 1;
			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

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);
   ~~~~~~^~~~~~~~~~~~~

Subtask #1
32.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Incorrect 7 ms 504 KB Output isn't correct
4 Incorrect 1367 ms 7312 KB Output isn't correct
5 Incorrect 1364 ms 7432 KB Output isn't correct
6 Incorrect 1379 ms 7544 KB Output isn't correct
7 Incorrect 1392 ms 7672 KB Output isn't correct
8 Incorrect 1368 ms 7800 KB Output isn't correct
9 Incorrect 1385 ms 7672 KB Output isn't correct
10 Incorrect 1376 ms 7672 KB Output isn't correct