fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct piatto{
  4. 	int somma;		//quando finisco di mangiare il piatto
  5. 	int inizio;		//quando inizio a mangiare il piatto
  6. 	int peso;		//valore del piatto
  7. 	bool operator<(piatto const& other) {
  8. 		return somma < other.somma;
  9. 	}
  10. };
  11. vector<pair<int,int>>Ore;	//vettore contenente (tempo in cui posso mangiare,quanto ho mangiato) di tutte le combinazioni
  12. int binarysearch(int val){	//ritorna indice del valore minore/uguale più a destra oppure -37 se non esiste
  13. 	int l=0,r=Ore.size(),mid,left=-37;
  14. 	while(l<=r){
  15. 		mid=((l+r)/2);
  16. 		if(Ore[mid].first==val){	//trovo il numero, non serve più cercare
  17. 			return mid;
  18. 		}
  19. 		if(Ore[mid].first<val){		//trovo un numero più piccolo cerco a destra
  20. 			left=mid;				//salvo questo indice, in caso fosse il più piccolo che trovo
  21. 			l=mid+1;	
  22. 		}else{						//trovo un numero più grande cerco a sinistra
  23. 			r=mid-1;
  24. 		}
  25. 	}
  26. 	return left;	//il numero ritornato sarebbe -37 in caso non avessi trovato nessun cibo che finisco di mangiare prima di quello attuale
  27. }
  28. int main(){
  29.  
  30. 	int N,ini,fin,peso;
  31. 	cin>>N;
  32. 	vector<piatto>P;			//vettore in cui salvo i piatti in ordine di fine
  33. 	piatto tmp;
  34.  
  35. 	for(int i=0;i<N;i++){
  36. 		cin>>ini>>peso>>fin;
  37. 		tmp.peso=peso;			//quanto vale il piatto
  38. 		tmp.inizio=ini;			//quando inizio a mangiare
  39. 		tmp.somma=(ini+fin);	//quando finisco di mangiare il piatto
  40. 		P.push_back(tmp);
  41. 	}
  42. 	sort(P.begin(),P.end());	//ordino i piatti a seconda di quando li finisico
  43.  
  44. 	for(int i=0;i<N;i++){
  45. 		if(Ore.size()==0){		//sono al primo piatto, non posso aver mangiato nulla prima
  46. 			Ore.push_back({P[i].somma,P[i].peso});
  47. 		}else{
  48. //devo trovare quanto ho mangiato finora nel migliore dei casi, l'elemento più a destra minore/uguale ad inizio
  49. 			int val=0,indx=binarysearch(P[i].inizio);
  50. 			if(indx!=-37){//attenzione se non trovo questo elemento!! (significa che non ho finitò piatti prima dell'arrivo di questo)
  51. 				val=Ore[indx].second;	//la soluzione fino al tempo in cui arriva il piatto
  52. 			}	
  53. 			val+=P[i].peso;				//mangio il piatto
  54. 			if(Ore[Ore.size()-1].first==P[i].somma){	//potrei finire due piatti nello stesso momento, cosa mi conviene fare?
  55. 				Ore[Ore.size()-1].second=max((val),Ore[Ore.size()-1].second);
  56. 			}else{
  57. 				if(val>Ore[Ore.size()-1].second){		//la soluzione di prima non mi conviene
  58. 					Ore.push_back({(P[i].somma),(val)});	
  59. 				}
  60. 			}	
  61. 		}
  62. 	}
  63. 	cout<<Ore[Ore.size()-1].second;
  64. 	//la soluzione si trova sicuramente nell'ultima posizione, 
  65. 	//in quanto se per un tempo in cui finisco un piatto esiste una soluzione migliore non verrà cambiato nulla
  66.  
  67. 	return 0;
  68. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4
6 24 3
8 16 5
17 4 1
11 11 2
stdout
copy 
24
https://ideone.com/O2K5Ob
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!