Szczegółowe omówienie zadania Dziwne cząsteczki:

Link do powyższego omówienia zadania Dziwne cząsteczki: https://youtu.be/jsaVtx5WQv0?t=1206
Link do treści zadania Dziwne cząsteczki: https://szkopul.edu.pl/problemset/problem/dwc/site

Zadanie Dziwne cząsteczki wykorzystuje  sumy prefiksowe: https://youtu.be/K4QtM9ycYl8?t=2489
Gdzie wykorzystuje się sumy prefiksowe? https://youtu.be/jsaVtx5WQv0?t=245

Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia Olimpiada Informatyczna OD PODSTAW: https://oki.org.pl/olimpiada-informatyczna-od-podstaw/
Wszystkie zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

–
Kod C++ programu "Dziwne cząsteczki", który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include<iostream>
#include<algorithm>
using namespace std;

const int limit1=1e6+7, limit2=1e4+4;
long long t[limit1];
long long sumpref[limit1];//suma prefiksowa posortowanego ciagu
long long zlicz[limit2];//suma prefiksowa tablicy zliczajacej

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long n, k;
    cin>>n>>k;
    for(int i=0; i<n; i++){
        cin>>t[i];
    }
    sort(t, t+n+1);//wartownik

    long long wynik=0;
    int ost=0;//ostatnia ogarnieta pozycja w tablicy zlicz
    for(int i=1; i<=n; i++){

        sumpref[i]=sumpref[i-1]+t[i];
        for(int j=ost+1; j<=t[i]; j++){
            zlicz[j]=zlicz[j-1];
        }
        ost=t[i];

        long long temp=zlicz[t[i]]-zlicz[max(t[i]-k-1, 0LL)];//roznica<=k
        wynik+=temp*k;
        wynik+=t[i]*(i-1-temp)-sumpref[i-1-temp];

        zlicz[t[i]]++;
    }

    cout<<wynik;
}