oj.uz

Submission #531981

# Submission time Handle Problem Language Result Execution time Memory
531981 2022-03-02T02:40:53 Z colazcy Vještica (COCI16_vjestica) C++17
160 / 160
 93 ms 1864 KB 
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#include <numeric>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e6 + 2333,inf = 0x3f3f3f3f;

int n,cnt[16][26],tmp[26],len[16],f[1 << 16];
char buf[maxn],*str[16],*now = buf;

int main(){
	// std::freopen("vjestica.in","r",stdin);
	// std::freopen("mag.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,0,n - 1){
		std::scanf("%s",str[i] = now);
		len[i] = std::strlen(str[i]);
		now += len[i] + 1;
	}
	rep(i,0,n - 1)debug("%s\n",str[i]);
	rep(i,0,n - 1)
		rep(j,0,len[i] - 1)
			cnt[i][str[i][j] - 'a']++;
	let full = (1 << n) - 1;
	std::memset(f,0x3f,sizeof(f));	
	f[0] = 0;
	rep(s,1,full){
		for(int t = s;t;t = (t - 1) & s)
			f[s] = std::min
			(f[s],f[t] + f[s ^ t]);
		std::fill_n(tmp,26,inf);
		rep(i,0,n - 1)
			if((s >> i) & 1)
				rep(j,0,25)
					tmp[j] = std::min(tmp[j],cnt[i][j]);
		let sum = std::accumulate(tmp,tmp + 26,0);
		f[s] -= sum;
		int slen = 0;
		rep(i,0,n - 1)
			if((s >> i) & 1)slen += len[i];
		f[s] = std::min(f[s],slen - sum * (__builtin_popcount(s) - 1));
	}
	std::printf("%d\n",1 + f[full]);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:21:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
vjestica.cpp:23:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   std::scanf("%s",str[i] = now);
      |   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Correct 82 ms 556 KB Output is correct
5 Correct 86 ms 716 KB Output is correct
6 Correct 88 ms 1248 KB Output is correct
7 Correct 89 ms 1664 KB Output is correct
8 Correct 88 ms 1864 KB Output is correct
9 Correct 92 ms 1664 KB Output is correct
10 Correct 93 ms 1752 KB Output is correct