Submission #796037

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796037	2023-07-28T05:15:44 Z	이성호(#10070)	Council (JOI23_council)	C++17	0 / 100	599 ms	13196 KB

council

#include <iostream>
using namespace std;
int dp[1<<20][2];
int cnt[20];
int mask[300005];
int ans[300005];
int df[300005], nd[300005];
int req;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, M; cin >> N >> M;
    int tmp[20] = {};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> tmp[j];
            cnt[j] += tmp[j];
        }
        for (int j = M - 1; j >= 0; j--) mask[i] = (mask[i] << 1) + tmp[j];
    }
    req = N / 2;
    int tot = (1 << M) - 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (mask[i] & (1 << j)) cnt[j]--;
        }
        for (int j = 0; j < M; j++) {
            if (cnt[j] == req) nd[i] |= 1 << j;
            else if (cnt[j] > req) df[i]++;
        }
        for (int j = 0; j < M; j++) {
            if (mask[i] & (1 << j)) cnt[j]++;
        }
    }
    for (int i = 0; i < N; i++) mask[i] = tot ^ mask[i];
    for (int i = 0; i < 19; i++) {
        if (i) {
            fill(&dp[0][0], &dp[1048575][2], 0);
        }
        for (int j = 0; j < N; j++) {
            if (j & (1 << i)) dp[mask[j]][1]++;
            else dp[mask[j]][0]++;
        }
        for (int i = 0; i < M; i++) {
            tot ^= 1 << i;
            for (int j = tot;; j = (j-1) & tot) {
                dp[j][0] += dp[j|1<<i][0];
                dp[j][1] += dp[j|1<<i][1];
                if (j == 0) break;
            }
            tot ^= 1 << i;
        }
        for (int i = 0; i < tot; i++) {
            dp[i][0] = dp[i][0] ? __builtin_popcount(i) : 0;
            dp[i][1] = dp[i][1] ? __builtin_popcount(i) : 0;
        }
        for (int i = 0; i < M; i++) {
            for (int j = (1<<i); j < (1 << M); j = (j+1) | (1<<i)) {
                dp[j][0] = max(dp[j][0], dp[j^(1<<i)][0]);
                dp[j][1] = max(dp[j][1], dp[j^(1<<i)][1]);
            }
        }
        for (int j = 0; j < N; j++) {
            if (j & (1 << i)) ans[j] = max(ans[j], dp[nd[j]][0]);
            else ans[j] = max(ans[j], dp[nd[j]][1]);
        }
    }
    for (int i = 0; i < N; i++) cout << ans[i] + df[i] << '\n';
    return 0;
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8552 KB	Output is correct
2	Correct	9 ms	8552 KB	Output is correct
3	Correct	6 ms	8532 KB	Output is correct
4	Correct	6 ms	8544 KB	Output is correct
5	Correct	599 ms	8532 KB	Output is correct
6	Correct	583 ms	8532 KB	Output is correct
7	Correct	576 ms	8652 KB	Output is correct
8	Correct	574 ms	8532 KB	Output is correct
9	Correct	592 ms	8652 KB	Output is correct
10	Correct	566 ms	8532 KB	Output is correct
11	Correct	571 ms	8652 KB	Output is correct
12	Correct	594 ms	8532 KB	Output is correct
13	Correct	6 ms	8532 KB	Output is correct
14	Correct	6 ms	8532 KB	Output is correct
15	Correct	6 ms	8532 KB	Output is correct
16	Correct	6 ms	8532 KB	Output is correct
17	Correct	6 ms	8532 KB	Output is correct
18	Incorrect	6 ms	8532 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8552 KB	Output is correct
2	Correct	9 ms	8552 KB	Output is correct
3	Correct	6 ms	8532 KB	Output is correct
4	Correct	6 ms	8544 KB	Output is correct
5	Correct	599 ms	8532 KB	Output is correct
6	Correct	583 ms	8532 KB	Output is correct
7	Correct	576 ms	8652 KB	Output is correct
8	Correct	574 ms	8532 KB	Output is correct
9	Correct	592 ms	8652 KB	Output is correct
10	Correct	566 ms	8532 KB	Output is correct
11	Correct	571 ms	8652 KB	Output is correct
12	Correct	594 ms	8532 KB	Output is correct
13	Correct	6 ms	8532 KB	Output is correct
14	Correct	6 ms	8532 KB	Output is correct
15	Correct	6 ms	8532 KB	Output is correct
16	Correct	6 ms	8532 KB	Output is correct
17	Correct	6 ms	8532 KB	Output is correct
18	Incorrect	6 ms	8532 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8532 KB	Output is correct
2	Correct	63 ms	12624 KB	Output is correct
3	Correct	62 ms	11372 KB	Output is correct
4	Correct	48 ms	11476 KB	Output is correct
5	Correct	61 ms	11364 KB	Output is correct
6	Incorrect	52 ms	13196 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8532 KB	Output is correct
2	Correct	63 ms	12624 KB	Output is correct
3	Correct	62 ms	11372 KB	Output is correct
4	Correct	48 ms	11476 KB	Output is correct
5	Correct	61 ms	11364 KB	Output is correct
6	Incorrect	52 ms	13196 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8532 KB	Output is correct
2	Correct	63 ms	12624 KB	Output is correct
3	Correct	62 ms	11372 KB	Output is correct
4	Correct	48 ms	11476 KB	Output is correct
5	Correct	61 ms	11364 KB	Output is correct
6	Incorrect	52 ms	13196 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8532 KB	Output is correct
2	Correct	63 ms	12624 KB	Output is correct
3	Correct	62 ms	11372 KB	Output is correct
4	Correct	48 ms	11476 KB	Output is correct
5	Correct	61 ms	11364 KB	Output is correct
6	Incorrect	52 ms	13196 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #7

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8552 KB	Output is correct
2	Correct	9 ms	8552 KB	Output is correct
3	Correct	6 ms	8532 KB	Output is correct
4	Correct	6 ms	8544 KB	Output is correct
5	Correct	599 ms	8532 KB	Output is correct
6	Correct	583 ms	8532 KB	Output is correct
7	Correct	576 ms	8652 KB	Output is correct
8	Correct	574 ms	8532 KB	Output is correct
9	Correct	592 ms	8652 KB	Output is correct
10	Correct	566 ms	8532 KB	Output is correct
11	Correct	571 ms	8652 KB	Output is correct
12	Correct	594 ms	8532 KB	Output is correct
13	Correct	6 ms	8532 KB	Output is correct
14	Correct	6 ms	8532 KB	Output is correct
15	Correct	6 ms	8532 KB	Output is correct
16	Correct	6 ms	8532 KB	Output is correct
17	Correct	6 ms	8532 KB	Output is correct
18	Incorrect	6 ms	8532 KB	Output isn't correct
19	Halted	0 ms	0 KB	-