oj.uz

답안 #490161

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490161 2021-11-26T02:35:25 Z Killer2501 Vještica (COCI16_vjestica) C++14
160 / 160
 91 ms 1472 KB 
#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "test"
#define pii pair<pll, pll>
using namespace std;
using ll = int;
const int  N = 16;
const ll mod = 1e8+7;
const ll base = 113;
const ll inf = 1e9;
ll m, n, t, k, a[N][N*2], tong, d[N], b[N*2], h[N], ans, dp[(1<<N)], cnt[(1<<N)];
vector<ll> adj[N];
vector<ll> kq, ask[N];
ll pw(ll k, ll n, ll md)
{
	ll total = 1;
	for(; n; n >>= 1)
	{
		if(n&1)total = total * k % md;
		k = k * k % md;
	}
	return total;
}
string s;
void sol()
{
    cin >> n;
    for(int i = 0; i < n;i ++)
    {
        cin >> s;
        for(int j = 0; j < s.length(); j ++)++a[i][s[j]-'a'];
    }
    for(int i = 0; i < (1<<n); i ++)
    {
        fill_n(b, 26, inf);
        for(int j = 0; j < n; j ++)
        {
            if((i >> j) & 1)
                for(int p = 0; p < 26; p ++)b[p] = min(b[p], a[j][p]);
        }
        for(int j = 0; j < 26; j ++)cnt[i] += b[j];
    }
    for(int i = 1; i < (1<<n); i ++)
    {
        if(__builtin_popcount(i) == 1)dp[i] = cnt[i];
        else
        {
            dp[i] = inf;
            for(int j = i; j; j = (j - 1) & i)
            {
                dp[i] = min(dp[i], dp[j]+dp[i^j]-cnt[i]);
            }
        }
    }
    cout << dp[(1<<n)-1]+1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message

vjestica.cpp: In function 'void sol()':
vjestica.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j = 0; j < s.length(); j ++)++a[i][s[j]-'a'];
      |                        ~~^~~~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
vjestica.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 85 ms 764 KB Output is correct
5 Correct 86 ms 904 KB Output is correct
6 Correct 85 ms 1104 KB Output is correct
7 Correct 85 ms 1264 KB Output is correct
8 Correct 91 ms 1472 KB Output is correct
9 Correct 89 ms 1216 KB Output is correct
10 Correct 85 ms 1208 KB Output is correct