Episodio 1: Un acquisto difficile (acquisti) 32/100

Sto provando a risolvere il problema acquisti, il mio codice prevede la creazione di due vettori di somme prefisse sp e n che contengono rispettivamente i pesi e il numero degli oggetti con un peso <= i. tramite una ricerca binaria individuo qual é il peso piú alto (lo nel codice) per cui posso portare tutti gli oggetti con peso <= ad esso, dopodiché calcolo quanti oggetti di peso lo+1 posso aggiungere.
La soluzione peró da solo 32/100 e non me ne viene in mente una meno dispendiosa e non ci ho trovato errori particolari

#include <vector>
using namespace std;

vector<long long> calcola(int T, int M, vector<long long> S, vector<long long> P) {
    vector<long long> R(M);
    vector<long long> sp(T);
    vector<long long> n(T);
    sp[0]=0;
    n[0]=S[0];
    for(int i=1;i<T;i++){
        sp[i]=sp[i-1]+S[i]*i;//peso di tutti gli oggetti fino al peso i
        n[i]=n[i-1]+S[i];   //numero totale di oggetti fino al peso i
    }
    for (int i = 0; i < M; i++) {
        int c=0;
        int lo=0;
        int hi=T-1;
        if (P[i]>sp[T-1]){  //abbiamo piú capacitá del peso totale degli oggetti,quindi possiamo portarli tutti
            c=n[T-1];
        }else{
            while (lo+1<hi){        //ricerca binaria per trovare fino a quale peso posso portare tutti gli oggetti piú leggeri
                int mid=(lo+hi)/2;
                if (P[i]>sp[mid]){
                    lo=mid;
                }else{
                    hi=mid;
                }
            }
            c+=n[lo];       //posso portare tutti gli oggetti di peso <= lo, quindi li aggiungo
            c+=(P[i]-sp[lo])/(lo+1);    //quanti oggetti posso portare di peso lo+1?
        }
        R[i] = c;    
        
    }

    return R;
}

La soluzione va bene dal punto di vista del tempo, un solo errore:

1 Mi Piace