Solução por Samyra Almeida
Conhecimentos prévios necessários:
- Sweep line
- BIT (Binary Indexed Tree, também conhecida como Árvore de Fenwick)
- Compressão de coordenadas
Chame de 
como a melhor lista de convidados. Por hora, vamos ignorar o quanto cada um pode doar. Segundo o enunciado do problema podemos concluir, para o conjunto 
, que:
Agora ordenaremos todos os candidatos em ordem crescente de beleza e em caso de empate o candidato com maior fortuna virá primeiro. Após isso, iremos realizar uma compressão de coordenadas nos valores de beleza e fortuna de todos os candidatos. Ao final da compressão, iremos juntar as doações de todos os candidatos que possuem a mesma beleza e a mesma fortuna, simultaneamente, pois eles sempre poderão ser convidados juntos.
Chame de 
fortuna do 
candidato, 
beleza do candidato e 
doação do candidato.
Agora, depois de comprimirmos nossa lista de candidatos, iremos processá-la. Para o candidato, iremos consultar na BIT a 
, ou seja, a maior doação que pode ser feita utilizando somente os candidatos que possuem uma fortuna menor que 
. Como os candidatos já estão em ordem crescente de beleza e decrescente de fortuna, não precisamos nos preocupar que a resposta do contenha algum candidato com maior beleza e/ou menor fortuna, pois estes ainda não foram processados.
Após isso, iremos atualizar nossa resposta para o máximo entre a resposta anterior e 
. Por fim, iremos fazer 
, ou seja, adicionamos a resposta do candidato na BIT.
Ao final, basta imprimir a resposta. Segue o código solução:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef unsigned long long ll; | |
| const int maxn = 1e5+10; | |
| struct node | |
| { | |
| ll b, f, d; | |
| bool operator<(const node& o) const | |
| { | |
| if(b != o.b) return b < o.b; // ordeno pela menor beleza | |
| else return f > o.f; // em caso de empate, pela maior fortuna | |
| } | |
| } c[maxn]; | |
| int n, m; | |
| ll bit[2*maxn]; // declaro a BIT com o dobro da quantidade de posições para o caso de todos os valores de fortuna e beleza serem diferentes | |
| vector<node> candidatos; | |
| void repeat() // junto os candidatos com a mesma fortuna e a mesma beleza | |
| { | |
| ll dd = 0LL; | |
| for(int i = 1 ; i <= n ; ++i) | |
| { | |
| if(c[i].b == c[i - 1].b && c[i].f == c[i - 1].f) // se o candidado i e i-1 possuem a mesma beleza e fortuna | |
| { | |
| dd += c[i].d; // somo as doações deles | |
| } | |
| else | |
| { | |
| if(i > 1) candidatos.push_back({c[i - 1].b, c[i - 1].f, dd}); // adiciono o candidato no vector | |
| dd = c[i].d; // atualizo a doação do i-ésimo candidato | |
| } | |
| } | |
| candidatos.push_back({c[n].b, c[n].f, dd}); // adiono o n-ésimo cadidato | |
| } | |
| void compress() // comprimo os valores de beleza e fortuna | |
| { | |
| map<ll, ll> M; | |
| for(int i = 1 ; i <= n ; ++i) M[c[i].b] = M[c[i].f] = 0LL; | |
| int amf = 0; | |
| for(auto it = M.begin() ; it != M.end() ; ++it) | |
| { | |
| it->second = ++amf; | |
| } | |
| for(int i = 1 ; i <= n ; ++i) | |
| { | |
| c[i].b = M[c[i].b]; | |
| c[i].f = M[c[i].f]; | |
| } | |
| m = amf; | |
| sort(c + 1, c + n + 1); // ordeno os candidatos | |
| repeat(); // junto os caras com a mesma beleza e fortuna | |
| } | |
| void update(int p, ll val) // update na BIT | |
| { | |
| for(int i = p; i <= m && i; i += (i & -i)) | |
| { | |
| bit[i] = max(bit[i], val); | |
| } | |
| } | |
| ll query(int p) // query na BIT | |
| { | |
| ll ans = 0LL; | |
| for(int i = p ; i > 0 ; i -= (i & -i)) | |
| { | |
| ans = max(bit[i], ans); | |
| } | |
| return ans; | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); | |
| cin >> n; | |
| for(int i = 1 ; i <= n ; ++i) | |
| { | |
| ll b, f, d; | |
| cin >> b >> f >> d; | |
| c[i] = {b, f, d}; | |
| } | |
| compress(); // comprimo os valores de beleza e fortuna | |
| ll ans = 0LL; | |
| for(auto u: candidatos) // processo os candidatos | |
| { | |
| ll at = query(u.f - 1); // consulto a melhor resposta para o u candidato | |
| at += u.d; // adiono a doação dele | |
| ans = max(at, ans); // atualizo a resposta | |
| update(u.f, at); // adiciono na BIT a resposta para u-ésimo cadidato | |
| } | |
| cout << ans << '\n'; // imprimo a resposta | |
| } |