oj.uz

Submission #412817

# Submission time Handle Problem Language Result Execution time Memory
412817 2021-05-27T15:42:35 Z rqi Vještica (COCI16_vjestica) C++14
160 / 160
 731 ms 1320 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define all(x) begin(x), end(x)

const int MOD = 1e9+7;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

int N;
map<char, int> m[20];
int dp[1<<16];


int getLCP(int sub){
	map<char, int> chars;
	bool isFirst = 1;
	for(int i = 0; i < N; i++){
		if(!((sub>>i)&1)) continue;
		if(isFirst){
			for(auto u: m[i]){
				chars[u.f] = u.s;
			}
			isFirst = 0;
		}
		else{
			for(auto u: chars){
				ckmin(chars[u.f], m[i][u.f]);
			}
		}
	}

	// for(auto u: chars){
	// 	cout << u.f << " " << u.s << "\n";
	// }

	int sum = 1;
	for(auto u: chars){
		sum+=u.s;
	}
	return sum;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	for(int i = 0; i < N; i++){
		string s;
		cin >> s;
		for(auto u: s){
			m[i][u]++;
		}
	}

	for(int i = 1; i < (1<<N); i++){
		//cout << "i: " << i << "\n";
		int bit_num = 0;
		for(int j = 0; j < N; j++){
			if((i>>j)&1){
				bit_num++;
			}
		}

		if(bit_num == 1){
			dp[i] = getLCP(i);
		}
		else{
			dp[i] = MOD;
			for(int j = i;; j=((j-1)&i)){
				if(i-j != 0 && j != 0){
					ckmin(dp[i], dp[j]+dp[i-j]);
				}
				if(j == 0) break;
			}
			dp[i]-=getLCP(i);
		}
	}
	cout << dp[(1<<N)-1] << "\n";


	// for(int i = 1; i < (1<<N); i++){
	// 	cout << i << " " << dp[i] << "\n";
	// }
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Correct 3 ms 320 KB Output is correct
4 Correct 322 ms 644 KB Output is correct
5 Correct 298 ms 620 KB Output is correct
6 Correct 731 ms 972 KB Output is correct
7 Correct 688 ms 1104 KB Output is correct
8 Correct 685 ms 1320 KB Output is correct
9 Correct 718 ms 1124 KB Output is correct
10 Correct 677 ms 1040 KB Output is correct