oj.uz

답안 #768848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768848 2023-06-28T18:33:01 Z danikoynov Council (JOI23_council) C++14
0 / 100
 1 ms 212 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 3e5 + 10, maxm = 21;
int n, m, imp[maxm], cnt[maxm];
bool a[maxn][maxm];
int dp[(1 << 11)][2];
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j], cnt[j] += a[i][j];
    if (m <= 10)
    {
        for (int mask = 0; mask < (1 << m); mask ++)
            dp[mask][0] = dp[mask][1] = -1;
        for (int i = 1; i <= n; i ++)
        {
            int can_mask = 0;
            for (int j = m - 1; j >= 0; j --)
                can_mask = can_mask * 2 + a[i][j];
            for (int mask = 0; mask < (1 << m); mask ++)
            {
                int sub = (mask & can_mask);
                int val = __builtin_popcount(sub);
                ///cout << i << " ---- " << mask << " " << val << endl;
                if (val > dp[mask][0])
                {
                    dp[mask][1] = dp[mask][0];
                    ///cout << "trans" << " " << val << endl;
                    dp[mask][0] = val;
                    ///cout << "here " << mask << " " << dp[mask][0] << " " << val << endl;
                }
                else if (val > dp[mask][1])
                {
                    dp[mask][1] = val;
                }
            }
        }

        for (int i = 1; i <= n; i ++)
        {
            int base = 0;
            for (int j = 0; j < m; j ++)
            {
                int cur = cnt[j] - a[i][j];
                if (cur >= n / 2)
                {
                    if ((cur - 1) < n / 2)
                        imp[j] = 1;
                    else
                        imp[j] = 0, base ++;
                }
                else
                {
                    imp[j] = 0;
                }

            }


            int mask = 0;
            for (int bit = m - 1; bit >= 0; bit --)
                mask = mask * 2 + imp[bit];
            int can_mask = 0;
            for (int j = m - 1; j >= 0; j --)
                can_mask = can_mask * 2 + a[i][j];
            int val = __builtin_popcount((can_mask & mask));
            //cout << i << " : " << val << " " << can_mask << " :: " << mask << endl;
            //cout << dp[mask][0] << " " << dp[mask][1] << endl;
            int best = dp[mask][0];
            if (val == best)
                best = dp[mask][1];
            cout << base + best << endl;


        }
    }
    else
    {

        for (int i = 1; i <= n; i ++)
        {
            int base = 0;
            for (int j = 0; j < m; j ++)
            {
                int cur = cnt[j] - a[i][j];
                if (cur >= n / 2)
                {
                    if ((cur - 1) < n / 2)
                        imp[j] = 1;
                    else
                        imp[j] = 0, base ++;
                }
                else
                {
                    imp[j] = 0;
                }

            }

            /**cout << "----" << endl;
            cout << i << endl;
            for (int bit = 0; bit < m; bit ++)
                cout << imp[bit] << " ";
            cout << endl;*/
            int best = -m;
            for (int p = 1; p <= n; p ++)
            {
                if (p == i)
                    continue;
                int sum = 0;
                for (int bit = 0; bit < m; bit ++)
                {
                    if (imp[bit] == 1)
                    {
                        if (a[p][bit] == 0)
                            sum ++;
                    }
                }

                best = max(best, sum);
            }

            cout << base + best << endl;


        }
    }
}

int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -