제출 #1087894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087894		kasdo	Izbori (COCI17_izbori)	C++17	80 / 80	32 ms	468 KiB

izbori

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define speed cin.tie (0) -> sync_with_stdio (0);ios_base::sync_with_stdio(false);cin.tie(0);
vector<int> v;
int n, m, k;
int a[105][20];
int ans = 1e9;
bool check()
{
    bool vis[m + 5] = {};
    for(auto i : v) vis[i] = 1;
    
    int f[m + 5] = {};
    pair<int, int> cur = {0, 0};
    for(int i=0; i<n; i++)
    {
        int x = 0;
        while (x < m && vis[a[i][x]]) x++;
        if (x == m) continue;
        f[a[i][x]]++;
        
        if (f[a[i][x]] > cur.first || (f[a[i][x]] == cur.first && a[i][x] < cur.second)) cur = {f[a[i][x]], a[i][x]};
    }
    
    if (cur.first != 0) return (cur.second == k);
    return 0;
}
void rec(int i, int cnt)
{
    if (i == m)
    {
        // for(auto i : v) cout<<i<<" ";
        // cout<<endl;
        bool x = check();
        // cout<<x<<endl;
        
        if (x) ans = min(ans, cnt);
        return;
    }
    
    v.push_back(i + 1);
    rec(i + 1, cnt + 1);
    v.pop_back();
    rec(i + 1, cnt);
}
void solve()
{
    cin>>n>>m>>k;
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>a[i][j];
        }
    }
    
    int ff[m + 5] = {};
    pair<int, int> mx = {0, 0};
    for(int i=0; i<n; i++)
    {
        ff[a[i][0]]++;
        if (ff[a[i][0]] > mx.first || (ff[a[i][0]] == mx.first && a[i][0] < mx.second)) mx = {ff[a[i][0]], a[i][0]};
    }
    cout<<mx.second<<endl;
    rec(0, 0);
    cout<<ans<<endl;
}
signed main ()
{
    speed
    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);

    int _ = 1;
    // cin>>_;

    while(_--) solve();

    return 0;
}

• Subtask 1: 80 / 80