Submission #48463494

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import std;
void main () {
    int H, W, K; readln.read(H, W, K);
    string[] S = new string[](H);
    foreach (i; 0..H) S[i] = readln.chomp;
    solve(H, W, K, S);
}
void solve (int H, int W, int K, string[] S) {
    /* 1Dなら貪欲で行ける -> 縦を全探索して貪欲すれば良い */
    int ans = int.max;
    /* チーム分け */
    int[] idx = new int[](H);
    string[][] T = new string[][](H, 0);
    int[] count = new int[](H);
    int check () {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import std;

void main () {
    int H, W, K; readln.read(H, W, K);
    string[] S = new string[](H);
    foreach (i; 0..H) S[i] = readln.chomp;

    solve(H, W, K, S);
}

void solve (int H, int W, int K, string[] S) {
    /* 1Dなら貪欲で行ける -> 縦を全探索して貪欲すれば良い */

    int ans = int.max;

    /* チーム分け */
    int[] idx = new int[](H);
    string[][] T = new string[][](H, 0);
    int[] count = new int[](H);

    int check () {
        int len = 0;
        foreach (x; idx) len = max(len, x+1);
        T.length = len;
        count.length = len;
        count[] = 0;
        foreach (ref t; T) t.length = 0;
        foreach (i, x; idx) T[x] ~= S[i];

        int res = cast(int) T.length-1;

        foreach (i; 0..W) {
            foreach (j, tt; T) {
                int sum = 0;
                foreach (t; tt) {
                    if (t[i] == '1') sum++;
                }
                if (K < count[j] + sum) {
                    count[] = 0;
                    res++;
                    break;
                }
            }

            foreach (j, tt; T) {
                int sum = 0;
                foreach (t; tt) {
                    if (t[i] == '1') sum++;
                }
                count[j] += sum;
            }

            foreach (c; count) if (K < c) return int.max;
        }

        return res;
    }

    foreach (e; enumSubset(H-1)) {
        int cur = 0;
        idx[] = 0;
        foreach (x; e) {
            idx[x] = -1;
        }

        foreach (ref x; idx) {
            if (x == -1) x = cur++;
            else x = cur;
        }

        ans = min(ans, check());
    }

    writeln(ans);
}

void read (T...) (string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

import std.format : format;
import std.exception : enforce;

struct SubsetIndexes {
    long bit;
    int right;
    long MAX;
    int[] res;
    this (int N) {
        MAX = 1<<N;
        res = new int[](N);
        right = 0;
    }

    auto front () const { return res[0..right]; }
    bool empty () const { return bit == MAX; }
    void popFront () {
        bit++;
        int i = 0;
        for (int j = 1, val = 0; j < MAX; j <<= 1, val++) if (0 < (j&bit)) res[i++] = val;
        right = i;
    }
}

struct SubsetItems (T) {
    import std.traits : ForeachType, Unconst;
    alias E = Unconst!(ForeachType!T)[];
    E arr;
    E res;
    int right;
    SubsetIndexes subsets;
    this (T arr) {
        this.arr = arr.dup;
        res = new E(arr.length);
        subsets = enumSubset(cast(int) arr.length);
    }

    auto front () const { return res[0..right]; }
    bool empty () const { return subsets.empty; }
    void popFront () {
        subsets.popFront;
        int i = 0;
        foreach (s; subsets.front) res[i++] = arr[s];
        right = i;
    }
}

auto enumSubset (T) (T arr)
if (is (T == E[], E) || is (T == E[n], E, size_t n))
{
    return SubsetItems!(T)(arr);
}

auto enumSubset (int N)
in {
    enforce(0 <= N && N <= 60, format("N must satisfy 0 <= N <= 60. Now N = %s.", N));
}
do {
    return SubsetIndexes(N);
}

Submission Info

Compile Error

/home/runner/.dub/packages/mir-algorithm/3.20.4/mir-algorithm/source/mir/serde.d(52,9): Deprecation: alias this for classes/interfaces is deprecated

Judge Result