Piano degli studi 70/100 (Execution timed out)

#include <iostream>
#include <algorithm>
using namespace std;

struct Trio {
	int i, f, v;
};

bool cmp(const Trio &A, const Trio &B) {
	return A.f < B.f;
}

int main() {
	ios::sync_with_stdio(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	
	int N; cin >> N;
	Trio C[N];
	for(auto &i : C) cin >> i.i >> i.f >> i.v;
	sort(C, C+N, cmp);
	
	int Dp[N]; Dp[0] = C[0].v;
	int Res = Dp[0];
	
	for(int i = 1; i < N; i++) {
		int Best = C[i].v;
		if(C[i].i > C[i-1].f) {
			for(int j = 0; j < i; j++) Best = max(Best, Dp[j]+C[i].v);
		} else {
			int L = 0, R = i-1;
			while(L <= R) {
				int Mid = (L+R)/2;
				if(C[i].i > C[Mid].f && C[i].i <= C[Mid+1].f) {
					for(int j = 0; j <= Mid; j++) Best = max(Best, Dp[j]+C[i].v);
					break;
				} else if(C[i].i > C[Mid].f) {
					L = Mid+1;
				} else if(C[i].i <= C[Mid].f) {
					R = Mid-1;
				}
			}
		}
		Dp[i] = Best;
		Res = max(Res, Dp[i]);
	}
	cout << Res;
}

Buonasera, stavo cercando di risolvere questo problema ma mi trovo davanti ad un bivio ovvero non so come altro ottimizzare l’algoritmo, o meglio, come implementare al meglio la ricerca binaria. Fino ad ora ho pensato di utilizzare la ricerca binaria per riuscire a trovarmi il punto esatto da dove si poteva cominciare a trovare la soluzione per il sotto problema, ma nonostante qualche lieve miglioramento purtroppo ottengo ancora un execution timed out in alcuni test case. Grazie per gli eventuali aiuti.

Guardando il codice si tratterebbe di ridurre la complessità.
Per come hai impostato il problema, ordinando i corsi per data fine, la dp viene con una complessità che porta in TLE. Pertanto consiglio prima di ordinare i corsi per data di inizio, poi di trovare il successivo di ogni corso con una bs ed infine con la dp (iterativa o ricorsiva) di trovare il massimo credito che si può accumulare.

Perdonami ma cosa intendi con trovare il successivo di ogni corso con la ricerca binaria?

Considera N = 4 corsi che dopo l’ordinamento per data d’inizio risulta:
N
2 4 10
3 10 30
5 6 15
7 8 20
il successivo del corso [0] che inizia il giorno 2 e termina il giorno 4 è il corso [2] che inizia il giorno 5 quindi per ogni corso:
[0] → [2]
[1] → [N]
[2] → [3]
[3] → [N]
utilizzo il valore dummy = N se il corso [x] non ne ha un successivo.
La ricerca di ogni successore si può dare in N^2 ma si va sicuramente in TLE oppure con una bs in NlogN visto che i corsi sono ordinati per data d’inizio.

Correggimi se sbaglio, quindi una volta aver trovato il successivo per ogni corso mi basta semplicemente stampare la somma dei valori più alta o devo fare anche qualcos’altro prima?

Esatto, da fare con una dp diversamente finisce in TLE.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Trio {
	int i, f, v;
};

bool cmp(const Trio &A, const Trio &B) {
	if(A.i != B.i) return A.i < B.i;
	else return A.f < B.f;
}

int main() {
	ios::sync_with_stdio(0);
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	
	int N, Res = -1; cin >> N;
	Trio C[N];
	for(auto &i : C) cin >> i.i >> i.f >> i.v;
	sort(C, C+N, cmp);
	
	vector<pair<int, int>> Succ(N, {-1, -1});
	for(int i = 0; i < N; i++) {
		if(Succ[i].second == -1) {
			Succ[i].second = C[i].v;
			Res = max(Res, Succ[i].second);
		} 
		int L = i+1, R = N-1;
		while(L <= R) {
			int Mid = (L+R)/2;
			if(C[Mid].i > C[i].f && C[Mid-1].i <= C[i].f) {
				Succ[i].first = Mid;
				Succ[Mid].second = max(Succ[Mid].second, Succ[i].second+C[Mid].v);
				Res = max(Res, Succ[Mid].second);
				break;
			} else if(C[Mid].i > C[i].f) R = Mid-1;
			else L = Mid+1;
		}
	}
}

Ho provato ad implementare il tuo consiglio ma evidentemente ho capito ben poco del procedimento da adottare. Sostanzialmente mi calcolo il successivo di ogni corso salvandomi (tanto per provare) anche il valore che si riesce ad ottenere arrivando fino al mid-esimo corso ma una volta arrivato a questo punto mi ritrovo bloccato e non so come continuare (sperando che almeno questa parte sia corretta). Però mi sorge un dubbio, ovvero che una volta arrivato, ipotizzando, ad un corso con inizio pari a C[i].f+1 come faccio a prendere, fra tutti i corsi che hanno inizio C[i].f+1, il migliore per il corso C[i]?

#include
#include
#include
using namespace std;

struct Trio {
int i, f, v;
};

bool cmp(const Trio &A, const Trio &B) {
/*
if(A.i != B.i) return A.i < B.i;
else return A.f < B.f;
*/
return A.i < B.i;
}

int main() {
ios::sync_with_stdio(0);
// freopen(“input.txt”, “r”, stdin);
// freopen(“output.txt”, “w”, stdout);

int N, Res = -1; cin >> N;
Trio C[N];
for(auto &i : C) cin >> i.i >> i.f >> i.v;
sort(C, C+N, cmp);

//vector<pair<int, int>> Succ(N, {-1, -1});
vector<int> Succ(N);
for(int i = 0; i < N; i++) {
    /*
	if(Succ[i].second == -1) {
		Succ[i].second = C[i].v;
		Res = max(Res, Succ[i].second);
	}
	*/
	//int L = i+1, R = N-1;
	int L = i, R = N-1;
	while(L <= R) {
		int Mid = (L+R)/2;
        /*
		if(C[Mid].i > C[i].f && C[Mid-1].i <= C[i].f) {
			Succ[i].first = Mid;
			Succ[Mid].second = max(Succ[Mid].second, Succ[i].second+C[Mid].v);
			Res = max(Res, Succ[Mid].second);
			break;
		} else */
		if(C[Mid].i > C[i].f) R = Mid-1;
		else L = Mid+1;
	}
	Succ[i] = R+1;
}

/*
* dp (td / bu) per trovare il credito max
*/

}

Premesso che si può fare la bs contemporaneamente alla dp, ma nel tuo codice siccome ci sono alcuni errori che portano a risultati sbagliati pertanto ho lasciato la bs esclusivamente per ricercare i successivi di ogni corso e ho corretto il valore di L.
Ho modificato anche la funzione cmp() basta semplicemente ordinare in base alla data d’inizio.
Ora che si hanno i successivi di ogni corso non rimane che trovare il massimo credito che si può maturare con la programmazione dinamica, se dp[i] indica il max credito maturato fino al corso i devi prima individuare il caso base e poi come passare da dp[i] → dp[i+1].