Submission #1241934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241934		Hanksburger	Council (JOI23_council)	C++20	100 / 100	1025 ms	174876 KiB

council

#include <bits/stdc++.h>
using namespace std;
int dp[2][1048576][21], a[300000], sum[20], n, m;
int add(int x, int y)
{
    if (!x)
        return y;
    if (!y)
        return x;
    return -1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            int x;
            cin >> x;
            a[i]|=x<<j;
            sum[j]+=x;
        }
        dp[1][a[i]][0]=add(dp[1][a[i]][0], i+1);
    }
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<(1<<m); j++)
        {
            for (int k=0; k<=m; k++)
            {
                if (j&(1<<i))
                    dp[i&1][j][k]=add(dp[(i&1)^1][j][k], dp[(i&1)^1][j^(1<<i)][k]);
                else
                    dp[i&1][j][k]=add(k?dp[(i&1)^1][j][k-1]:0, dp[(i&1)^1][j^(1<<i)][k]);
            }
        }
    }
    for (int i=0; i<n; i++)
    {
        int x=0, ans=0;
        for (int j=0; j<m; j++)
        {
            int diff=sum[j]-((a[i]>>j)&1);
            if (diff>n/2)
                ans++;
            if (diff!=n/2)
                x|=1<<j;
        }
        for (int j=m; j>=0; j--)
        {
            if (dp[(m&1)^1][x][j] && dp[(m&1)^1][x][j]!=i+1)
            {
                cout << ans+j << '\n';
                break;
            }
        }
    }
}

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