oj.uz

답안 #726433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
726433 2023-04-18T22:10:06 Z YugiHacker Vještica (COCI16_vjestica) C++17
160 / 160
 454 ms 1552 KB 
/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn
#define bit(mask,i) ((mask>>i)&1)
using namespace std;
int n;
string s[16];
int cnt[16][26];
int f[1 << 16];
int val(int mask)
{
    vector <int> mi(26, 1e9);
    f0 (i, n) if (bit(mask, i))
        f0 (j, 26) mi[j] = min(mi[j], cnt[i][j]);
    return accumulate(mi.begin(), mi.end(), 0);
}
int calc(int mask)
{
    int &ans = f[mask];
    if (ans != -1) return ans;
    int common = val(mask);
    if (__builtin_popcount(mask) == 1) return common;
    ans = 1e9;
    for (int i=(mask - 1) & mask; i; i = (i-1) & mask)
        ans = min(ans, calc(i) + calc(mask ^ i) - common);
    return ans;
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    f0 (i, n)
    {
        cin >> s[i];
        for (char c:s[i]) cnt[i][c-'a']++;
    }
    memset(f, -1, sizeof f);
    cout << calc((1 << n) - 1) + 1;
}

Compilation message

vjestica.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      | ^~~~

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 420 ms 596 KB Output is correct
5 Correct 437 ms 844 KB Output is correct
6 Correct 429 ms 1108 KB Output is correct
7 Correct 421 ms 1492 KB Output is correct
8 Correct 416 ms 1552 KB Output is correct
9 Correct 403 ms 1488 KB Output is correct
10 Correct 454 ms 1508 KB Output is correct