oj.uz

Submission #133483

# Submission time Handle Problem Language Result Execution time Memory
133483 2019-07-20T22:27:46 Z tdwn Vještica (COCI16_vjestica) C++17
160 / 160
 351 ms 1276 KB 
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
int cnt[30][30], n;
int dp[(1<<16)];
int min_val[30];

int solve(int mask) {
	if(dp[mask] != -1) return dp[mask];

	if(__builtin_popcount(mask) == 1) {
		for(int i=0;i<n;i++) {
			if(mask&(1<<i)) {
				int sum = 0;
				for(int j=0;j<26;j++) {
					sum += cnt[i][j];
				}
				return dp[mask] = sum;
			}
		}
	}

	for(int i=0;i<26;i++) min_val[i] = INT_MAX;
	int intersection = 0;
	for(int i=0;i<n;i++) {
		if(mask & (1<<i)) {
			for(int j=0;j<26;j++)
				min_val[j] = min(min_val[j], cnt[i][j]);
		}
	}

	for(int i=0;i<26;i++) intersection += min_val[i];

	dp[mask] = 10000000;
	int b = 0;
	do {
		dp[mask] = min(dp[mask], solve(b) + solve(mask^b) - intersection);
	} while (b=(b-mask)&mask);
	return dp[mask];
}

int main() {
	cin>>n;
	string str;
	for(int i=0;i<n;i++) {
		cin>>str;
		for(int j=0;j<str.length();j++) {
			cnt[i][int(str[j]-'a')]++;
		}
	}

	memset(dp,-1,sizeof(dp));
	cout<<solve((1<<n)-1) + 1;
}

Compilation message

vjestica.cpp: In function 'int solve(int)':
vjestica.cpp:40:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  } while (b=(b-mask)&mask);
           ~^~~~~~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<str.length();j++) {
               ~^~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 310 ms 732 KB Output is correct
5 Correct 315 ms 760 KB Output is correct
6 Correct 325 ms 888 KB Output is correct
7 Correct 332 ms 1108 KB Output is correct
8 Correct 340 ms 1276 KB Output is correct
9 Correct 336 ms 1144 KB Output is correct
10 Correct 351 ms 1272 KB Output is correct