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