oj.uz

Submission #857987

# Submission time Handle Problem Language Result Execution time Memory
857987 2023-10-07T08:50:13 Z danikoynov Diversity (CEOI21_diversity) C++14
14 / 100
 7000 ms 5788 KB 
#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 (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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 4548 KB Output is correct
8 Correct 29 ms 4444 KB Output is correct
9 Correct 265 ms 4524 KB Output is correct
10 Correct 3429 ms 4520 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 4552 KB Output is correct
4 Correct 34 ms 4696 KB Output is correct
5 Correct 292 ms 4940 KB Output is correct
6 Correct 3393 ms 5600 KB Output is correct
7 Correct 3350 ms 5536 KB Output is correct
8 Correct 3387 ms 5552 KB Output is correct
9 Correct 3365 ms 5788 KB Output is correct
10 Correct 3443 ms 5592 KB Output is correct
11 Correct 3364 ms 5576 KB Output is correct
12 Correct 3395 ms 5600 KB Output is correct
13 Correct 3409 ms 5580 KB Output is correct
14 Correct 3400 ms 5568 KB Output is correct
15 Correct 3360 ms 5564 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 4552 KB Output is correct
4 Correct 34 ms 4696 KB Output is correct
5 Correct 292 ms 4940 KB Output is correct
6 Correct 3393 ms 5600 KB Output is correct
7 Correct 3350 ms 5536 KB Output is correct
8 Correct 3387 ms 5552 KB Output is correct
9 Correct 3365 ms 5788 KB Output is correct
10 Correct 3443 ms 5592 KB Output is correct
11 Correct 3364 ms 5576 KB Output is correct
12 Correct 3395 ms 5600 KB Output is correct
13 Correct 3409 ms 5580 KB Output is correct
14 Correct 3400 ms 5568 KB Output is correct
15 Correct 3360 ms 5564 KB Output is correct
16 Execution timed out 7069 ms 4448 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 4 ms 4552 KB Output is correct
4 Correct 34 ms 4696 KB Output is correct
5 Correct 292 ms 4940 KB Output is correct
6 Correct 3393 ms 5600 KB Output is correct
7 Correct 3350 ms 5536 KB Output is correct
8 Correct 3387 ms 5552 KB Output is correct
9 Correct 3365 ms 5788 KB Output is correct
10 Correct 3443 ms 5592 KB Output is correct
11 Correct 3364 ms 5576 KB Output is correct
12 Correct 3395 ms 5600 KB Output is correct
13 Correct 3409 ms 5580 KB Output is correct
14 Correct 3400 ms 5568 KB Output is correct
15 Correct 3360 ms 5564 KB Output is correct
16 Execution timed out 7069 ms 4448 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 4548 KB Output is correct
8 Correct 29 ms 4444 KB Output is correct
9 Correct 265 ms 4524 KB Output is correct
10 Correct 3429 ms 4520 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 4 ms 4552 KB Output is correct
14 Correct 34 ms 4696 KB Output is correct
15 Correct 292 ms 4940 KB Output is correct
16 Correct 3393 ms 5600 KB Output is correct
17 Correct 3350 ms 5536 KB Output is correct
18 Correct 3387 ms 5552 KB Output is correct
19 Correct 3365 ms 5788 KB Output is correct
20 Correct 3443 ms 5592 KB Output is correct
21 Correct 3364 ms 5576 KB Output is correct
22 Correct 3395 ms 5600 KB Output is correct
23 Correct 3409 ms 5580 KB Output is correct
24 Correct 3400 ms 5568 KB Output is correct
25 Correct 3360 ms 5564 KB Output is correct
26 Execution timed out 7069 ms 4448 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 4548 KB Output is correct
8 Correct 29 ms 4444 KB Output is correct
9 Correct 265 ms 4524 KB Output is correct
10 Correct 3429 ms 4520 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 4 ms 4552 KB Output is correct
14 Correct 34 ms 4696 KB Output is correct
15 Correct 292 ms 4940 KB Output is correct
16 Correct 3393 ms 5600 KB Output is correct
17 Correct 3350 ms 5536 KB Output is correct
18 Correct 3387 ms 5552 KB Output is correct
19 Correct 3365 ms 5788 KB Output is correct
20 Correct 3443 ms 5592 KB Output is correct
21 Correct 3364 ms 5576 KB Output is correct
22 Correct 3395 ms 5600 KB Output is correct
23 Correct 3409 ms 5580 KB Output is correct
24 Correct 3400 ms 5568 KB Output is correct
25 Correct 3360 ms 5564 KB Output is correct
26 Execution timed out 7069 ms 4448 KB Time limit exceeded
27 Halted 0 ms 0 KB -