Submission #8534290


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }

int solve(int n, int m, const vector<string> & p) {
    vector<bool> mergeable(1 << n, true);
    REP (s, 1 << n) {
        if (__builtin_popcount(s) <= 1) {
            // nop
        } else if (__builtin_popcount(s) == 2) {
            int a = __builtin_ctz(s);
            int b = __builtin_ctz(s & ~ (1 << a));
            REP (i, m) {
                if (p[a][i] != '*' and p[b][i] != '*' and p[a][i] != p[b][i]) {
                    mergeable[s] = false;
                }
            }
        } else {
            REP (a, n) if (s & (1 << a)) {
                REP (b, a) if (s & (1 << b)) {
                    if (not mergeable[(1 << a) | (1 << b)]) {
                        mergeable[s] = false;
                    }
                }
            }
        }
    }

    vector<int> dp(1 << n, INT_MAX);
    REP (s, 1 << n) {
        dp[s] = __builtin_popcount(s);
        REP3 (t, 1, s + 1) if ((s & t) == t) {
            if (mergeable[t]) {
                chmin(dp[s], dp[s & ~ t] + 1);
            }
        }
    }
    return dp.back();
}

int main() {
    int n, m; cin >> n >> m;
    vector<string> p(n);
    REP (i, n) {
        cin >> p[i];
    }
    cout << solve(n, m, p) << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 天下一文字列集合
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1661 Byte
Status
Exec Time 210 ms
Memory 1792 KB

Judge Result

Set Name Score / Max Score Test Cases
small 20 / 20 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt
medium 30 / 30 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 01_medium100.txt, 01_medium101.txt, 01_medium102.txt, 01_medium103.txt, 01_medium104.txt, 01_medium105.txt, 01_medium106.txt, 01_medium107.txt, 01_medium108.txt, 01_medium109.txt, 01_medium110.txt, 01_medium111.txt, 01_medium112.txt, 01_medium113.txt, 01_medium114.txt, 01_medium115.txt, 01_medium116.txt, 01_medium117.txt, 01_medium118.txt, 01_medium119.txt, 01_medium120.txt, 01_medium121.txt, 01_medium122.txt, 01_medium123.txt, 01_medium124.txt, 01_medium125.txt, 01_medium126.txt, 01_sample0.txt
All 50 / 50 00_small100.txt, 00_small101.txt, 00_small102.txt, 00_small103.txt, 00_small104.txt, 00_small105.txt, 00_small106.txt, 00_small107.txt, 00_small108.txt, 00_small109.txt, 00_small110.txt, 00_small111.txt, 00_small112.txt, 00_small113.txt, 00_small114.txt, 00_small115.txt, 00_small116.txt, 00_small117.txt, 01_medium100.txt, 01_medium101.txt, 01_medium102.txt, 01_medium103.txt, 01_medium104.txt, 01_medium105.txt, 01_medium106.txt, 01_medium107.txt, 01_medium108.txt, 01_medium109.txt, 01_medium110.txt, 01_medium111.txt, 01_medium112.txt, 01_medium113.txt, 01_medium114.txt, 01_medium115.txt, 01_medium116.txt, 01_medium117.txt, 01_medium118.txt, 01_medium119.txt, 01_medium120.txt, 01_medium121.txt, 01_medium122.txt, 01_medium123.txt, 01_medium124.txt, 01_medium125.txt, 01_medium126.txt, 01_sample0.txt, 02_large100.txt, 02_large101.txt, 02_large102.txt, 02_large103.txt, 02_large104.txt, 02_large105.txt, 02_large106.txt, 02_large107.txt, 02_large108.txt, 02_large109.txt, 02_large110.txt, 02_large111.txt, 02_large112.txt, 02_large113.txt, 02_large114.txt, 02_large115.txt, 02_large116.txt, 02_large117.txt, 02_large118.txt, 02_large119.txt, 02_large120.txt, 02_large121.txt, 02_large122.txt, 02_large123.txt, 02_large124.txt, 02_large125.txt, 02_large126.txt, 02_large127.txt, 02_large128.txt, 02_large129.txt, 02_large130.txt
Case Name Status Exec Time Memory
00_small100.txt 1 ms 256 KB
00_small101.txt 1 ms 256 KB
00_small102.txt 1 ms 256 KB
00_small103.txt 1 ms 256 KB
00_small104.txt 1 ms 256 KB
00_small105.txt 1 ms 256 KB
00_small106.txt 1 ms 256 KB
00_small107.txt 1 ms 256 KB
00_small108.txt 1 ms 256 KB
00_small109.txt 1 ms 256 KB
00_small110.txt 1 ms 256 KB
00_small111.txt 1 ms 256 KB
00_small112.txt 1 ms 256 KB
00_small113.txt 1 ms 256 KB
00_small114.txt 1 ms 256 KB
00_small115.txt 1 ms 256 KB
00_small116.txt 1 ms 256 KB
00_small117.txt 1 ms 256 KB
01_medium100.txt 112 ms 256 KB
01_medium101.txt 111 ms 256 KB
01_medium102.txt 107 ms 256 KB
01_medium103.txt 110 ms 256 KB
01_medium104.txt 108 ms 256 KB
01_medium105.txt 107 ms 256 KB
01_medium106.txt 111 ms 256 KB
01_medium107.txt 108 ms 256 KB
01_medium108.txt 4 ms 256 KB
01_medium109.txt 1 ms 256 KB
01_medium110.txt 1 ms 256 KB
01_medium111.txt 110 ms 256 KB
01_medium112.txt 107 ms 256 KB
01_medium113.txt 108 ms 256 KB
01_medium114.txt 1 ms 256 KB
01_medium115.txt 110 ms 256 KB
01_medium116.txt 111 ms 256 KB
01_medium117.txt 107 ms 256 KB
01_medium118.txt 107 ms 256 KB
01_medium119.txt 107 ms 256 KB
01_medium120.txt 108 ms 256 KB
01_medium121.txt 108 ms 256 KB
01_medium122.txt 109 ms 256 KB
01_medium123.txt 109 ms 256 KB
01_medium124.txt 111 ms 256 KB
01_medium125.txt 111 ms 256 KB
01_medium126.txt 112 ms 256 KB
01_sample0.txt 1 ms 256 KB
02_large100.txt 161 ms 1792 KB
02_large101.txt 159 ms 1792 KB
02_large102.txt 157 ms 1792 KB
02_large103.txt 161 ms 1792 KB
02_large104.txt 157 ms 1792 KB
02_large105.txt 158 ms 1792 KB
02_large106.txt 120 ms 640 KB
02_large107.txt 109 ms 384 KB
02_large108.txt 30 ms 256 KB
02_large109.txt 1 ms 256 KB
02_large110.txt 2 ms 256 KB
02_large111.txt 191 ms 1792 KB
02_large112.txt 177 ms 1792 KB
02_large113.txt 116 ms 512 KB
02_large114.txt 165 ms 1792 KB
02_large115.txt 159 ms 1792 KB
02_large116.txt 168 ms 1792 KB
02_large117.txt 4 ms 512 KB
02_large118.txt 176 ms 1792 KB
02_large119.txt 187 ms 1792 KB
02_large120.txt 197 ms 1792 KB
02_large121.txt 205 ms 1792 KB
02_large122.txt 210 ms 1792 KB
02_large123.txt 203 ms 1792 KB
02_large124.txt 192 ms 1792 KB
02_large125.txt 182 ms 1792 KB
02_large126.txt 174 ms 1792 KB
02_large127.txt 170 ms 1792 KB
02_large128.txt 170 ms 1792 KB
02_large129.txt 208 ms 1792 KB
02_large130.txt 167 ms 1792 KB