제출 #1318318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318318		spetr	Diversity (CEOI21_diversity)	C++20	0 / 100	0 ms	332 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vl vector<long long>
#define pl pair<long long, long long>

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, q;
    if (!(cin >> n >> q)) return 0;
    
    // 1. Načtení a spočítání četností
    vl input_nums(n);
    map<ll, ll> counts;
    for (ll i = 0; i < n; i++){
        cin >> input_nums[i];
        counts[input_nums[i]]++;
    }
    
    ll l_query, r_query;
    cin >> l_query >> r_query; // Jen načteme, v Q=1 se nepoužívá specificky jinak než přes celé pole

    // 2. Vytvoření párů {četnost, druh}
    vector<pl> pary;
    for (auto const& [species, count] : counts) {
        pary.push_back({count, species});
    }
    
    // 3. Seřazení od nejméně častých po nejčastější
    sort(pary.begin(), pary.end());
    
    // 4. Konstrukce optimálního rozložení (Mountain shape)
    // Použijeme deque pro vkládání z krajů
    deque<ll> final_blocks;
    
    // Procházíme seřazené páry a střídavě dáváme doleva a doprava
    for (int i = 0; i < pary.size(); i++) {
        ll count = pary[i].first;
        ll species = pary[i].second;
        
        // Pokud je 'i' sudé, dáme na začátek (vlevo), liché na konec (vpravo)
        // Tím dostaneme nejmenší na úplné kraje a největší doprostřed.
        if (i % 2 == 0) {
            // Přidáme blok zleva
            for(int k=0; k<count; k++) final_blocks.push_front(species);
        } else {
            // Přidáme blok zprava
            for(int k=0; k<count; k++) final_blocks.push_back(species);
        }
    }
    
    // Převedeme deque zpět na vector pro DP výpočet
    vl nums(final_blocks.begin(), final_blocks.end());

    // 5. DP výpočet (tento byl správně, jen na špatně seřazeném poli)
    vl dp(n, 1);
    
    // Base case: dp[0] = 1 (jeden prvek má diverzitu 1)
    
    for (ll i = 1; i < n; i++){
        if (nums[i] == nums[i-1]){
            // Stejný druh jako předchozí -> nepřidává novou diverzitu do existujících suffixů
            dp[i] = dp[i-1] + 1;
        }
        else{
            // Jiný druh -> pro všechny suffixy končící na i-1 se diverzita zvýší o 1
            // + vznikne 1 nový suffix (samotný prvek i)
            // Celkem se přičte: (i) + 1 = i + 1
            dp[i] = dp[i-1] + (i + 1);
        }
    }
    
    ll suma = 0;
    for (ll i = 0; i < n; i++){
        suma += dp[i];
    }
    
    cout << suma << "\n";

    return 0;
}

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