oj.uz

Submission #541848

# Submission time Handle Problem Language Result Execution time Memory
541848 2022-03-24T15:24:28 Z new_acc Vještica (COCI16_vjestica) C++14
160 / 160
 1658 ms 1352 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll M=1e6+10;
const int N=1e5+10;
const ll SS=1<<20;
const ll INFi=1e9;
const ll INFl=1e12;
const int k=17;
int t[k][26],dl[N];
int dp[(1<<k)+1];
void solve(){
	int n;
	cin>>n;
	int xd=0;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++) t[i][int(s[j])-96]++;
		dl[i]=s.size();
	}
	for(int i=1;i<(1<<n);i++){
		if(__builtin_popcount(i)==1){
			dp[i]=0;
			continue;
		}
		int ile=0;
		for(int k=1;k<=26;k++){
			int mini=INFi;
			for(int j=0;j<n;j++){
				if(!((1<<j)&i)) continue;
				mini=min(mini,t[j+1][k]);
			}
			ile+=mini;
		}
		vi pom;
		int sum=0;
		for(int j=0;j<n;j++) if((1<<j)&i) sum+=dl[j+1],pom.push_back(j);
		if(sum==ile*__builtin_popcount(i)){
			dp[i]=ile*(__builtin_popcount(i)-1);
			continue;
		}
		for(int j=1;j<(1<<pom.size())-1;j++){
			int mask=0;
			for(int k=0;k<pom.size();k++) if((1<<k)&j) mask+=(1<<pom[k]);
			dp[i]=max(dp[i],dp[mask]+dp[i-mask]+ile);
		}
	}
	int res=0;
	for(int i=1;i<=n;i++) res+=dl[i];
	cout<<res-dp[(1<<n)-1]+1<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

vjestica.cpp: In function 'void solve()':
vjestica.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<s.size();j++) t[i][int(s[j])-96]++;
      |               ~^~~~~~~~~
vjestica.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int k=0;k<pom.size();k++) if((1<<k)&j) mask+=(1<<pom[k]);
      |                ~^~~~~~~~~~~
vjestica.cpp:20:6: warning: unused variable 'xd' [-Wunused-variable]
   20 |  int xd=0;
      |      ^~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1648 ms 660 KB Output is correct
5 Correct 1657 ms 808 KB Output is correct
6 Correct 1622 ms 788 KB Output is correct
7 Correct 1655 ms 1224 KB Output is correct
8 Correct 1647 ms 1352 KB Output is correct
9 Correct 1649 ms 1196 KB Output is correct
10 Correct 1658 ms 1212 KB Output is correct