Submission #857988

#	Time	Username	Problem	Language	Result	Execution time	Memory
857988		danikoynov	Diversity (CEOI21_diversity)	C++14	10 / 100	7080 ms	5028 KiB

diversity

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

using namespace std;
typedef long long ll;

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

const int maxn = 3e5 + 10;

int n, q, a[maxn], cnt[maxn], m, val[maxn], used[maxn];

    vector < ll > groups;
    ll ans;

void check()
{
    ll tot = 0;
    /**for (int i = 0; i < m; i ++)
        cout << val[i] << " ";
    cout << endl;*/
    for (int i = 0; i < m; i ++)
    {
        ll bf = 0;
        for (int j = 0; j < i; j ++)
            bf = max(bf, groups[val[j]]);
        ll af = 0;
        for (int j = i + 1; j < m; j ++)
            af = max(af, groups[val[j]]);
        if (groups[val[i]] < bf && groups[val[i]] < af)
        {
            return;
        }
    }
        for (ll i = 0; i < m; i ++)
        for (ll j = i + 1; j < m; j ++)
    {
        tot = tot + groups[val[i]] * groups[val[j]] * (j - i + 1);
    }

    for (int i = 0; i < m; i ++)
    {
        ll cur = groups[i];
        tot = tot + cur * (cur + 1) / 2;
    }
    ans = min(ans, tot);
}

void perm(int pos)
{
    if (pos == m)
        check();
    else
    {
        for (int i = 0; i < m; i ++)
        {
            if (!used[i])
            {
                val[pos] = i;
                used[i] = 1;
                perm(pos + 1);
                used[i] = 0;
                val[pos] = 0;
            }
        }
    }
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    int l, r;
    cin >> l >> r;

    for (int i = 1; i <= n; i ++)
        cnt[a[i]] ++;


    for (int i = 1; i <= n; i ++)
        if (cnt[i] > 0)
        groups.push_back((ll)(cnt[i]));

        ans = 1e18;
    m = groups.size();
    perm(0);
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}
/**
4 1
1 1 1 1
1 2
2 4

4 1
2 1 3 2
1 4

*/

Compilation message (stderr)

diversity.cpp: In function 'void solve()':
diversity.cpp:86:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |     for (int i = 1; i <= n; i ++)
      |     ^~~
diversity.cpp:90:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   90 |         ans = 1e18;
      |         ^~~

• Subtask 1: 0 / 4
• Subtask 2: 10 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36