fork download
copy 
  1. import sys
  2.  
  3. it = sys.stdin.read().split()
  4.  
  5.  
  6. n = int(it[0])
  7.  
  8. jobs = []
  9. idx = 1
  10. for _ in range(n):
  11.     s = int(it[idx])
  12.     f = int(it[idx + 1])
  13.     v = int(it[idx + 2])
  14.     jobs.append([s, f, v])
  15.     idx += 3
  16.  
  17. jobs.sort(key=lambda x: x[1])
  18.  
  19. sdj = [[-1, -1, 0]] + jobs
  20.  
  21. q = [0] * (n + 1)
  22. for j in range(1, n + 1):
  23.     sj = sdj[j][0]
  24.     for i in range(j - 1, 0, -1):
  25.         if sdj[i][1] <= sj:
  26.             q[j] = i
  27.             break
  28.  
  29. opt = [0] * (n + 1)
  30. for j in range(1, n + 1):
  31.     vj = sdj[j][2]
  32.  
  33.     inj = vj + opt[q[j]]
  34.     exj = opt[j - 1]
  35.  
  36.     if inj >= exj: 
  37.         opt[j] = inj
  38.     else:
  39.         opt[j] = exj
  40.  
  41. s = []
  42. c = n
  43. while c > 0:
  44.     vj = sdj[c][2]
  45.  
  46.     if vj + opt[q[c]] >= opt[c - 1]:
  47.         s.append(c)
  48.         c = q[c]
  49.     else:
  50.         c -= 1 
  51.  
  52. print(s)
  53.  
Success #stdin #stdout 0.11s 14140KB
comments (?)
stdin
copy 
10
2 6 15
6 9 1
4 5 7
8 15 12
1 4 6
5 12 8
6 9 3
10 18 6
15 29 8
5 17 3
stdout
copy 
[10, 7, 3]
https://ideone.com/zpx0c5
language:
Python 3 (python  3.12)
created:
12 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!