oj.uz

답안 #243259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243259 2020-06-30T16:11:15 Z ajpiano Vještica (COCI16_vjestica) C++14
160 / 160
 90 ms 1536 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

struct word{
    int letters[26];
};

const int large = 1e9;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vi dp(1<<n);
    vi nones[n+1];
    F0R(i,1,(1<<n)-1){
        int a = __builtin_popcount(i);
        nones[a].push_back(i);
    }
    vector<word> words;
    FOR(i,n){
        word w;
        string s; cin >> s;
        FOR(j,26) w.letters[j] = 0;
        for(auto &a:s) w.letters[a-'a']++;
        words.push_back(w);
    }
    FOR(i,n){
        int tot = 0;
        FOR(j,26) tot += words[i].letters[j];
        dp[nones[1][i]] = tot;
    }
    F0R(bits,2,n){
        for(auto & mask:nones[bits]){
            word a;
            FOR(i,26) a.letters[i] = large;
            FOR(i,n){
                if(mask&(1<<i)){
                    FOR(j,26){
                        a.letters[j] = min(a.letters[j],words[i].letters[j]);
                    }
                }
            }
            int tot = 0;
            FOR(i,26) tot += a.letters[i];
            int best = large;
            int ptr = mask;
            ptr = (ptr-1)&mask;
            while(ptr > 0){
                best = min(best, dp[ptr]+dp[mask^ptr]);
                ptr = (ptr-1)&mask;
            }
            dp[mask] = best-tot;
        }
    }
    int k = (1<<n)-1;
    cout << dp[k]+1 << "\n";
    return 0;
}

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 85 ms 1068 KB Output is correct
5 Correct 85 ms 1104 KB Output is correct
6 Correct 87 ms 1308 KB Output is correct
7 Correct 86 ms 1496 KB Output is correct
8 Correct 83 ms 1536 KB Output is correct
9 Correct 89 ms 1536 KB Output is correct
10 Correct 90 ms 1408 KB Output is correct