oj.uz

Submission #52000

# Submission time Handle Problem Language Result Execution time Memory
52000 2018-06-23T07:13:05 Z Adhyyan1252 Vještica (COCI16_vjestica) C++11
160 / 160
 372 ms 3448 KB 
#include<bits/stdc++.h>

using namespace std;
#define NMAX 16
string s[NMAX];
vector<vector<int> > f;
int n;
int  dp[(1<<NMAX)];

int rec(int mask){
	if(dp[mask] != -1) return dp[mask];
	
	int lcp = 0;
	for(int i = 0; i < 26; i++){
		int cur = INT_MAX;
		for(int j = 0; j < n; j++){
			if(mask&(1<<j))
				cur = min(cur, f[j][i]);
		}
		lcp += cur;
	}
	
	dp[mask] = INT_MAX;
	for(int sub = (mask-1)&mask; sub > 0; sub = (sub-1)&mask){
		dp[mask] = min(dp[mask], rec(sub) + rec(sub^mask) - lcp);
	}
	return dp[mask];
}

int main(){
	cin>>n;
	f.resize(n, vector<int>(26, 0));
	for(int i = 0; i < n; i++){
		cin>>s[i];
		for(int j = 0; j < s[i].length(); j++){
			f[i][s[i][j]-'a']++;
		}
	}
	for(int i = 0; i < (1<<n); i++) dp[i] = -1;
	dp[0] = 0;
	for(int i = 0; i < n; i++){
		dp[(1<<i)] = s[i].length();
	}
	cout<<rec((1<<n)-1) + 1<<endl;
//	for(int i = 0; i < (1<<n); i++){
//		cout<<i<<" : "<<dp[i]<<endl;
//	}
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < s[i].length(); j++){
                  ~~^~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 251 ms 792 KB Output is correct
5 Correct 236 ms 1052 KB Output is correct
6 Correct 253 ms 1536 KB Output is correct
7 Correct 372 ms 1908 KB Output is correct
8 Correct 251 ms 2592 KB Output is correct
9 Correct 268 ms 2988 KB Output is correct
10 Correct 242 ms 3448 KB Output is correct