Aiuto per Sabbie mobili (preoii_sabbia)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Sabbie mobili.

ricevo 39 punti ottenendo solo output corretto e TLE, anche se penso che il mio codice non faccia troppe operazioni. (evidentemente non sto capendo qualcosa).
Sto facendo una sorta di dp su dag, dove ogni nodo i rappresenta la somma dei palloni appesi ai primi i - 1 edifici.
Ho provato a implementare il grafo sia con vettore di adiacenza, sia in quest’ altro modo sperando di ricavare qualcosa a livello di tempo, ma non va comunque.

Ecco il mio codice:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void s(vector<ll>V){
	for(ll i : V) cout << i << " ";
	cout << endl;
}
long long alleggerisci(int N, int M, vector<int> V, vector<int> L, vector<int> R, vector<long long> K) {
    vector<ll>px(N + 1, 0), pv(N + 1, 0);
	vector<vector<pair<ll, int>>>endat(N + 1);
	for(int i = 1; i < N + 1; i++){
		pv[i] = pv[i - 1] + 1LL * V[i - 1];
	} 
	for(int i = 0; i < M; i++){
		int l = L[i], r = R[i];
		ll d = max(0LL, pv[r + 1] - pv[l] - K[i]);
		endat[r + 1].push_back({d, l});
	}
	for(int i = 1; i <= N; i++){
		px[i] = px[i - 1];
		for(auto [w, idx] : endat[i]){
			px[i] = max(px[i], px[idx] + w);
		}
	}
	return px[N];
}

Grazie mille in anticipo!

2

Probabilmente e’ lenta la allocazione dei vector… ti consiglio di sortare l’array con std::sort (anche se peggiora la complessita’ potrebbe essere piu’ veloce), oppure scrivendo counting sort bene (senza vector di vector come lo stai facendo ora).

Counting sort scritto bene sarebbe questo:

void counting_sort(vector<int> &V) {
    const int N = V.size();

    vector<int> p(N), f(N);
    for(int i = 0; i < N; ++i) {
        f[V[i]] += 1;
    }

    for(int i = 1; i < N; ++i) {
        f[i] += f[i - 1];
    }

    for(int i = N - 1; i >= 0; i--) {
        p[f[V[i]]--] = i;
    }

    vector<int> tmp(N);
    for(int i = 0; i < N; ++i) {
        tmp[p[i]] = V[i];
    }

    swap(V, tmp);
}
3

ciao, non capisco perché dici di ordinare il vettore, perché la posizione di ogni elemento è importante e cambiarla cambierebbe il risultato. (almeno così ho capito). puoi spiegarmi questa cosa? grazie

4

Ciao, nel tuo codice hai l’array endat, in cui ti salvi per ogni r i range che hanno R_i = r, per poi iterare su ogni r e “visitare” i range del blocco r. Questo e’ equivalente a ordinare i range per R_i. In particolare, come lo hai implementato te stai facendo questo ordinamento in O(N) con counting sort, pero’ i vettori possono essere lenti quando sforano la capacita’ (in particolare i vector bidimensionali) e quindi fai tante operazioni. Ti consiglio o di usare std::sort (che come ho detto, probabilmente e’ piu’ veloce del tuo codice attuale anche se peggiore la complessita’), o l’implementazione di counting sort che ti ho mandato.