oj.uz

답안 #796037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
796037 2023-07-28T05:15:44 Z 이성호(#10070) Council (JOI23_council) C++17
0 / 100
 599 ms 13196 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -