답안 #925980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925980	2024-02-12T12:14:57 Z	GrindMachine	Diversity (CEOI21_diversity)	C++17	14 / 100	7000 ms	9452 KB

diversity

#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;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,q; cin >> n >> q;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    
    {
        ll l,r; cin >> l >> r;
    }

    vector<ll> b;
    rep(i,n) b.pb(a[i]);
    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    rep(i,n) a[i] = lower_bound(all(b),a[i])-b.begin();
    ll m = sz(b);

    vector<ll> order(m);
    rep(i,m) order[i] = i;

    vector<ll> cnt(m);
    rep(i,n) cnt[a[i]]++;

    ll ans = inf2;

    do{

        ll i = 1;
        ll cost = 0;

        trav(x,order){
            ll c = cnt[x];
            cost += i*(n-i+1);
            if(c > 1){
                ll mx = n-(i+1)+1;
                ll mn = n-(i+c-1)+1;
                assert(mn <= mx);
                cost += mx*(mx+1)/2-mn*(mn-1)/2;
            }
        
            i += c;            
        }

        amin(ans,cost);

    } while(next_permutation(all(order)));

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	496 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	6 ms	348 KB	Output is correct
9	Correct	53 ms	428 KB	Output is correct
10	Correct	581 ms	344 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	19 ms	2388 KB	Output is correct
5	Correct	124 ms	4600 KB	Output is correct
6	Correct	1323 ms	8916 KB	Output is correct
7	Correct	1324 ms	8912 KB	Output is correct
8	Correct	1348 ms	9164 KB	Output is correct
9	Correct	1340 ms	9452 KB	Output is correct
10	Correct	1322 ms	9428 KB	Output is correct
11	Correct	1319 ms	8292 KB	Output is correct
12	Correct	1313 ms	8912 KB	Output is correct
13	Correct	1321 ms	8656 KB	Output is correct
14	Correct	1320 ms	7892 KB	Output is correct
15	Correct	1310 ms	8148 KB	Output is correct

Subtask #3
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	19 ms	2388 KB	Output is correct
5	Correct	124 ms	4600 KB	Output is correct
6	Correct	1323 ms	8916 KB	Output is correct
7	Correct	1324 ms	8912 KB	Output is correct
8	Correct	1348 ms	9164 KB	Output is correct
9	Correct	1340 ms	9452 KB	Output is correct
10	Correct	1322 ms	9428 KB	Output is correct
11	Correct	1319 ms	8292 KB	Output is correct
12	Correct	1313 ms	8912 KB	Output is correct
13	Correct	1321 ms	8656 KB	Output is correct
14	Correct	1320 ms	7892 KB	Output is correct
15	Correct	1310 ms	8148 KB	Output is correct
16	Execution timed out	7002 ms	344 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	19 ms	2388 KB	Output is correct
5	Correct	124 ms	4600 KB	Output is correct
6	Correct	1323 ms	8916 KB	Output is correct
7	Correct	1324 ms	8912 KB	Output is correct
8	Correct	1348 ms	9164 KB	Output is correct
9	Correct	1340 ms	9452 KB	Output is correct
10	Correct	1322 ms	9428 KB	Output is correct
11	Correct	1319 ms	8292 KB	Output is correct
12	Correct	1313 ms	8912 KB	Output is correct
13	Correct	1321 ms	8656 KB	Output is correct
14	Correct	1320 ms	7892 KB	Output is correct
15	Correct	1310 ms	8148 KB	Output is correct
16	Execution timed out	7002 ms	344 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	496 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	6 ms	348 KB	Output is correct
9	Correct	53 ms	428 KB	Output is correct
10	Correct	581 ms	344 KB	Output is correct
11	Correct	0 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	19 ms	2388 KB	Output is correct
15	Correct	124 ms	4600 KB	Output is correct
16	Correct	1323 ms	8916 KB	Output is correct
17	Correct	1324 ms	8912 KB	Output is correct
18	Correct	1348 ms	9164 KB	Output is correct
19	Correct	1340 ms	9452 KB	Output is correct
20	Correct	1322 ms	9428 KB	Output is correct
21	Correct	1319 ms	8292 KB	Output is correct
22	Correct	1313 ms	8912 KB	Output is correct
23	Correct	1321 ms	8656 KB	Output is correct
24	Correct	1320 ms	7892 KB	Output is correct
25	Correct	1310 ms	8148 KB	Output is correct
26	Execution timed out	7002 ms	344 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Subtask #6
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	496 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	6 ms	348 KB	Output is correct
9	Correct	53 ms	428 KB	Output is correct
10	Correct	581 ms	344 KB	Output is correct
11	Correct	0 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	19 ms	2388 KB	Output is correct
15	Correct	124 ms	4600 KB	Output is correct
16	Correct	1323 ms	8916 KB	Output is correct
17	Correct	1324 ms	8912 KB	Output is correct
18	Correct	1348 ms	9164 KB	Output is correct
19	Correct	1340 ms	9452 KB	Output is correct
20	Correct	1322 ms	9428 KB	Output is correct
21	Correct	1319 ms	8292 KB	Output is correct
22	Correct	1313 ms	8912 KB	Output is correct
23	Correct	1321 ms	8656 KB	Output is correct
24	Correct	1320 ms	7892 KB	Output is correct
25	Correct	1310 ms	8148 KB	Output is correct
26	Execution timed out	7002 ms	344 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

답안 #925980

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 8.0

Subtask #4 0 / 16.0

Subtask #5 0 / 26.0

Subtask #6 0 / 36.0

Subtask #1
4.0 / 4.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 8.0

Subtask #4
0 / 16.0

Subtask #5
0 / 26.0

Subtask #6
0 / 36.0