Submission #1257956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257956		NHristov	Council (JOI23_council)	C++20	33 / 100	4094 ms	16868 KiB

council

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 3e5 + 5;
const int M = 20;

int n, m;

struct Save
{
    int mx1, pos1;
    int mx2, pos2;
};

bool vote[N][M];
int cnt[M];

Save dp[(1 << M)];

Save upd(Save a, Save b)
{
    Save ret;

    ret = {0, 0, 0, 0};

    ret.mx1 = max(a.mx1, b.mx1);

    if (ret.mx1 == a.mx1)
    {
        ret.pos1 = a.pos1;
    }
    else
    {
        ret.pos1 = b.pos1;
    }

    if (a.mx1 > ret.mx2 && a.pos1 != ret.pos1)
    {
        ret.mx2 = a.mx1;
        ret.pos2 = a.pos1;
    }

    if (b.mx1 > ret.mx2 && b.pos1 != ret.pos1)
    {
        ret.mx2 = b.mx1;
        ret.pos2 = b.pos1;
    }

    if (a.mx2 > ret.mx2 && a.pos2 != ret.pos1)
    {
        ret.mx2 = a.mx2;
        ret.pos2 = a.pos2;
    }

    if (b.mx2 > ret.mx2 && b.pos2 != ret.pos1)
    {
        ret.mx2 = b.mx2;
        ret.pos2 = b.pos2;
    }

    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        int mask = 0;

        for (int q = 0; q < m; q++)
        {
            cin >> vote[i][q];

            if (!vote[i][q])
            {
                mask += (1 << q);
            }
            else
            {
                cnt[q]++;
            }
        }

        for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
        {
            dp[submask] = upd(dp[submask], Save{__builtin_popcount(submask), i, 0, 0});
        }

        dp[0] = upd(dp[0], Save{0, i, 0, 0});
    }

    for (int i = 0; i < m; i++)
    {
        for (int mask = (1 << i); mask < (1 << m); mask = (mask + 1) | (1 << i))
        {
            dp[mask] = upd(dp[mask], dp[mask ^ (1 << i)]);
        }
    }

    for (int i = 0; i < n; i++)
    {
        int good = 0, mask = 0;

        for (int q = 0; q < m; q++)
        {
            int rem = cnt[q] - vote[i][q];

            if (rem > n / 2)
            {
                good++;
            }

            if (rem == n / 2)
            {
                mask |= (1 << q);
            }
        }

        int ans = good;

        if (dp[mask].pos1 == i)
        {
            ans += dp[mask].mx2;
        }
        else
        {
            ans += dp[mask].mx1;
        }

        cout << ans << endl;
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 19 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22