oj.uz

답안 #42753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42753 2018-03-03T19:05:34 Z ekrem Vještica (COCI16_vjestica) C++
48 / 160
 23 ms 4872 KB 
/*
ID: ekrem
LANG: C++
TASK: 
*/
#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;
#define foreach(kk,gg) for(__typeof(gg.begin())kk=gg.begin();kk!=gg.end();kk++)
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define SET(a, b) memset(a, b, sizeof a)
#define heap priority_queue
#define orta (bas+son>>1)
#define endll puts("")
#define mp make_pair
#define pb push_back
#define sag (k+k+1)
#define sol (k+k)
#define endl '\n'
#define nd second
#define st first
#define y1 ekrem
#define y2 merke
typedef int don;
#define int long long int
inline int read(){int x;scanf(" %lld",&x);return x;}

typedef pair < int , int > ii;
typedef vector < int > vi;
typedef vector < ii > vii;

const int inf = 1e9 + 7;
const int linf = 1e18 + 7;

const int N = 4e4 + 5;

int n, dp[N], c[20][30], h[30];
string s[N];

int bul(int bit){
	int top = 0;
	FOR(i, 0, 'z' - 'a')h[i] = inf;
	FOR(i, 0, n)
		if(bit&(1<<i))
			FOR(ch, 0, 'z' - 'a')
				h[ch] = min(h[ch], c[i][ch]);
	FOR(i, 0, 'z' - 'a')
		if(h[i] < inf)
			top += h[i];
	return top;
}

int coz(int bit){
	if(dp[bit] != -1)
		return dp[bit];
	int bas = bul(bit);
	if((bit & (-bit)) == bit)
		return dp[bit] = bas;
	int ans = inf;
	for(int i = (bit - 1)&bit; i > 0; i = (i - 1)&bit)
		ans = min(ans, coz(i) +  coz(bit^i) - bas);
	return dp[bit] = ans;
}

don main(){
	// freopen("input.in", "r", stdin);freopen("input.out", "w", stdout);
	SET(dp, -1);
	n = read() - 1;
	FOR(i, 0, n)
		cin >> s[i];
	FOR(i, 0, n)
		FOR(j, 0, (int)s[i].length() - 1)
			c[i][s[i][j] - 'a']++;
	cout << coz((1<<(n + 1)) - 1) + 1 << endl;
	return 0;
}

Compilation message

vjestica.cpp: In function 'long long int read()':
vjestica.cpp:45:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 inline int read(){int x;scanf(" %lld",&x);return x;}
                                          ^

Subtask #1
48.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1788 KB Output is correct
2 Correct 3 ms 1888 KB Output is correct
3 Correct 3 ms 1960 KB Output is correct
4 Runtime error 5 ms 3644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 3840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 4332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 4588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 23 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 20 ms 4844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 20 ms 4872 KB Execution killed with signal 11 (could be triggered by violating memory limits)