oj.uz

Submission #298984

# Submission time Handle Problem Language Result Execution time Memory
298984 2020-09-14T11:37:41 Z TadijaSebez Vještica (COCI16_vjestica) C++11
160 / 160
 104 ms 1144 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=16;
const int A=26;
int cnt[N][A],mn[A];
int dp[1<<N];
const int L=1000050;
char s[L];
int main(){
	int n;
	scanf("%i",&n);
	for(int i=0;i<n;i++){
		scanf("%s",s+1);
		int m=strlen(s+1);
		for(int j=1;j<=m;j++){
			cnt[i][s[j]-'a']++;
		}
		dp[1<<i]=m;
	}
	for(int i=0;i<1<<n;i++)if(__builtin_popcount(i)>1){
		dp[i]=1e9;
		for(int j=i;;){
			j=(j-1)&i;
			if(j==0)break;
			dp[i]=min(dp[i],dp[j]+dp[i^j]);
		}
		for(int j=0;j<A;j++)mn[j]=1e9;
		for(int j=0;j<n;j++)if(i>>j&1){
			for(int z=0;z<A;z++)mn[z]=min(mn[z],cnt[j][z]);
		}
		for(int j=0;j<A;j++)dp[i]-=mn[j];
	}
	printf("%i\n",dp[(1<<n)-1]+1);
	return 0;
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
vjestica.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%s",s+1);
      |   ~~~~~^~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 96 ms 632 KB Output is correct
5 Correct 102 ms 632 KB Output is correct
6 Correct 98 ms 888 KB Output is correct
7 Correct 100 ms 1144 KB Output is correct
8 Correct 99 ms 1064 KB Output is correct
9 Correct 104 ms 1016 KB Output is correct
10 Correct 102 ms 988 KB Output is correct