제출 #1088467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1088467		HishamAlshehri	Izbori (COCI17_izbori)	C++17	80 / 80	11 ms	464 KiB

izbori

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")

constexpr int maxn = 1000001;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, m, k;
int a[101][16], mn = 20;
bool take[16];

void f(int i, int cnt) {
    if (i > m) {
        short frq[16] = {};
        for (int j = 0; j < n; j++) {
            for (int c = 0; c <= cnt; c++){
                if (!take[a[j][c]]) {
                    frq[a[j][c]]++; 
                    break;
                }
            }
        }
        short mx = 0, mxi = 1;
        for (int j = 1; j <= m; j++)
        {
            if (frq[j] > mx)
            {
                mx = frq[j];
                mxi = j;
            }
        }
        if (mxi == k)
        {
            // int ans = 0;
            // for (int j = 0; j < 16; j++) {
            //     if (take[j]) ans++;
            // }
            mn = min(mn, cnt);
        }
        return;
    }
    if (i != k) {
        take[i] = 1;
        f(i + 1, cnt + 1);
        take[i] = 0;
    }
    f(i + 1, cnt);
    return;
}

signed main() 
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int frq[16] = {};
    for (int i = 0; i < n; i++) frq[a[i][0]]++;
    short mx = 1, mxi = 1;
    for (int j = 1; j <= m; j++)
    {
        if (frq[j] > mx)
        {
            mx = frq[j];
            mxi = j;
        }
    }
    cout << mxi << "\n";
    f(1, 0);
    cout << mn;
}

• Subtask 1: 80 / 80