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 $$S = \{S_1, S_2, S_3 …, S_{K-1}, S_K\}$$ 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 $$S$$, que:
- $$B_1 \leq B_2 \leq B_3 \leq … \leq B_{K-1} \leq B_K$$
- $$F_1 \leq F_2 \leq F_3 \leq … \leq F_{K-1} \leq F_K$$
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 $$U_{i_f} =$$ fortuna do $$U_i$$ candidato, $$U_{i_b} =$$ beleza do $$U_i$$ candidato e $$U_{i_d} =$$ doação do $$U_i$$ candidato.
Agora, depois de comprimirmos nossa lista de candidatos, iremos processá-la. Para o $$U_i$$ candidato, iremos consultar na BIT a $$query(U_{i_f} – 1)$$, ou seja, a maior doação que pode ser feita utilizando somente os candidatos que possuem uma fortuna menor que $$U_{i_f}$$. Como os candidatos já estão em ordem crescente de beleza e decrescente de fortuna, não precisamos nos preocupar que a resposta do $$U_i$$ 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 $$query(U_{i_f} – 1) + U_{i_d}$$. Por fim, iremos fazer $$update(U_{i_f}, query(U_{i_f} – 1) + U_{i_d})$$, ou seja, adicionamos a resposta do $$U_i$$ candidato na BIT.
Ao final, basta imprimir a resposta. Segue o código solução:
| #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 | |
| } |
