fork download 
  1. program sushi; (*ordino il vettore P in ordine crescente di tempo di fine; poi applico PROCEDURA RICERCALOWER*)
  2. Uses Math;
  3. const MAXN=100002;
  4. type piatto = record
  5.                    inizio:int64;
  6.                    durata:int64;
  7.                    peso:int64;
  8.                    fine:int64;
  9.                 end;
  10.      elenco = array[0.. MAXN-1] of int64;           
  11.      table = array[0..MAXN-1] of piatto;          
  12. var N,i,id:Longint;
  13.     ricordafine : int64;
  14.     T : table; 
  15.     S,W,D,E, DP, ricordaindice :elenco;  (*array riferiti ai piatti Start, Weigth, Durata, End*)
  16.  
  17.  
  18. Procedure scambia (var a,b: int64);
  19. var x:int64;
  20. begin
  21.    x:=a;
  22.    a:=b;
  23.    b:=x;
  24. end;  
  25.  
  26. Procedure ordinamento (estremoi,estremos: int64; var v : elenco; var u:elenco; ordinato:boolean);
  27. var inf, sup, medio:int64;
  28.     pivot :int64;
  29. begin
  30.     inf:=estremoi;
  31.     sup:=estremos;
  32.     medio:= (estremoi+estremos) div 2;
  33.     pivot:=v[medio];
  34.     repeat
  35.       if (ordinato) then
  36.          begin
  37.             while (v[inf]<pivot) do  inf:=inf+1;
  38.             while (v[sup]>pivot) do  sup:=sup-1;
  39.          end;
  40.       if inf<=sup then
  41.        begin
  42.          scambia(v[inf],v[sup]);
  43.          scambia(u[inf],u[sup]);
  44.          inf:=inf+1;
  45.          sup:=sup-1;
  46.        end;
  47.     until inf>sup;
  48.     if (estremoi<sup) then ordinamento(estremoi,sup,v,u,ordinato);
  49.     if (inf<estremos) then ordinamento(inf,estremos,v,u,ordinato);
  50. end;
  51. Procedure ricercaLower (var w:elenco; target:int64); (*ritorna indice del valore minore/uguale a target oppure -1 se non esiste*)
  52.   var m,start,eend: int64;
  53.  
  54.  begin  
  55.    start:=0; eend:=N-1 ; m:=-1;
  56.    while start<=eend do
  57.            begin
  58.                   m:=(start + eend) div 2;
  59.                   if w[m]<=target then begin id:=m;  start:=m+1 end
  60.                                   else  if w[m]>target then   eend:=m-1; 
  61.            end;
  62.    if eend=-1 then id:=-1;
  63.  end;
  64.  
  65. begin
  66.  
  67.    readln(N);
  68.    for i:=0 to N-1 do begin ricordaindice[i]:=i;  DP[i]:=0; end;
  69.    for i:=0 to N-1 do
  70.       begin
  71.         { dish on table }
  72.          readln(S[i],W[i],D[i]);
  73.          E[i]:=S[i]+D[i];
  74.          T[i].inizio:=S[i];
  75.          T[i].durata:=D[i];
  76.          T[i].peso:=W[i];
  77.          T[i].fine:=E[i];
  78.       end;
  79.     ordinamento(0,N-1,E, ricordaindice,true);
  80.     for i:=0 to N-1 do  (*faccio scorrere gli elementi dell'array P ordinato secondo la fine dei piatti, per ciascun piatto di P considero l'ora di inizio e cerco se c'è un piatto che finisce prima; se c'è,  posso mangiare il piatto considerato se conveniente rispetto a quelli che ho mangiato fino a quel momento, altrimenti il piatto potrebbe essere il primo che arriva e allora lo prendo comunque, salvo poi controllare se ci sono altri piatti che iniziano dopo, ma finiscono contemporaneamente, e hanno il peso più conveniente*)
  81.                 begin
  82.                     ricordafine:=T[ricordaindice[i]].inizio;
  83.                     ricercaLower(E, ricordafine);
  84.                     if id<>-1 then
  85.                                 DP[i]:=max (DP[i-1],DP[id]+T[ricordaindice[i]].peso)
  86.                               else 
  87.                                 begin 
  88.                                   if i=0 then DP[i]:=T[ricordaindice[i]].peso
  89.                                          else DP[i]:=max (DP[i-1],T[ricordaindice[i]].peso)
  90.                                 end;         
  91.                 end;
  92.    writeln(DP[N-1]);   
  93. end.
Success #stdin #stdout 0s 6608KB
comments (?)
stdin 
4
6 24 3
8 16 5
17 4 1
11 11 2
stdout 
39
https://ideone.com/d7dni4
language:
Pascal (fpc 3.0.4)
created:
6 hours 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!