PiratasParcial.cpp

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int N,K; cin >> N >> K;

    //guarda as moedas que cada um ganha na última distribuição que deu certo
    //é mantido ordenado
    vector<int> anterior;
    //quantos piratas vão ser jogados no mar caso a distribuição atual dê errado
    int jogados = 0;
    //quantas moedas o pirata mais velho que não foi jogado ganha
    int resposta = 0;

    for(int i = 1; i <= N; i++)
    {
        //custo para comprar (i -1)/2 votos
        int custo = 0;

        //o custo será a soma das (i-1)/2 menores quantidades de moedas ganhas na anterior
        for(int j = 0; j < (i - 1)/2; j++)
            custo += anterior[j] + 1;

        //se o custo for maior do que a quantidade de moedas, o pirata i não consegue fazer a distribuição
        if(custo > K)
        {
            //considero que i vai ser jogado ao mar
            jogados++;
            //determino que ele "ganha -1 moedas"
            anterior.push_back(-1);
        }
        else
        {
            //como o i consegue comprar votos o suficiente, resetamos o número de piratas jogados ao mar para 0
            jogados = 0;

            //como i conseguiu comprar os votos, ele é o pirata mais velho a não ser jogado, então a resposta muda
            resposta = K - custo;

            //vamos reconstruir o vetor da distribuição usando um vector auxiliar
            vector<int> aux;

            //coloco com quantas moedas o pirata mais velho fica
            aux.push_back(K - custo);

            //agora, quem eu comprei o voto ganha 1 moeda a mais do que ganhava
            for(int j = 0; j < (i - 1)/2; j++)
                aux.push_back(anterior[j] + 1);

            //quem eu não comprei o voto ganha 0 moedas
            while(aux.size() < i)
                aux.push_back(0);

            anterior = aux;
        }

        sort(anterior.begin(),anterior.end());
    }
    cout << jogados << " " << resposta << "\n";
}