fork download
copy 
  1. uses math;
  2. const
  3.   fi='hirehp.inp';
  4.   fo='hirehp.out';
  5.   maxn=5*trunc(1e5);
  6.   oo=trunc(1e18);
  7. var
  8.   tree : array[1..4*maxn] of int64;
  9.   idleaf : array[1..maxn] of longint;
  10.   i,j,n : longint;
  11.   f : array[1..maxn] of int64;
  12.   t,p : array[1..maxn] of longint;
  13. procedure build(k,l,r : longint);
  14.   var m : longint;
  15.   begin
  16.     if l = r then
  17.       begin
  18.         idleaf[l] := k;
  19.         exit;
  20.       end;
  21.     m := (l+r) div 2;
  22.     build(k*2,l,m);
  23.     build(k*2+1,m+1,r);
  24.   end;
  25. procedure update(j: longint; x : int64);
  26.   begin
  27.     i := idleaf[j];
  28.     while i > 0 do
  29.       begin
  30.         tree[i] := min(tree[i] , x);
  31.         i := i div 2;
  32.       end;
  33.   end;
  34. function get(k,l,r,i,j : longint) : int64;
  35.   var m  :  longint;
  36.       tg1,tg2 : int64;
  37.   begin
  38.     if (i>r) or (j<l) then exit(oo);
  39.     if (i<=l) and (j>=r) then exit(tree[k]);
  40.     m := (l+r) div 2;
  41.     tg1 := get(k*2,l,m,i,j);
  42.     tg2 := get(k*2+1,m+1,r,i,j);
  43.     get := min(tg1,tg2);
  44.   end;
  45. procedure main;
  46. var i : longint;
  47. begin
  48. //  assign(input,fi);reset(input);
  49. //assign(output,fo);rewrite(output);
  50.   read(n);
  51.   for i := 1 to n do read(t[i] , p[i]);
  52.   for i := 1 to 4*n do tree[i] := oo;
  53.   build(1,1,n);
  54.   update(t[1] , p[1]);
  55.   f[1] := p[1];
  56.   for i := 2 to n do
  57.     begin
  58.       f[i] := get(1,1,n,i-1,n) + p[i];
  59.       update(t[i] , f[i]);
  60.     end;
  61.   writeln(get(1,1,n,n,n));
  62.   //close(input);close(output);
  63. end;
  64. begin
  65.   main;
  66. end.
  67.  
Time limit exceeded #stdin #stdout 5s 8368128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JgFljT
language:
Pascal (fpc 3.0.4)
created:
6 years ago
visibility:
secret

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!