Submission #7067099


Source Code Expand

Copy
import math

n, m = map(int, input().split())

jobs = []
for i in range(n):
	day, reward = map(int, input().split())
	if m- day + 1 > 0:
		jobs.append((m - day + 1, reward))

jobs.sort(key = lambda x:(-x[1],-x[0]))

def find(i):
	global parent
	while i != parent[i]:
		parent[i] = parent[parent[i]]
		i = parent[i]
	return i 

def union(x, y):	# small, big
	global parent
	parent_x = find(x)
	parent_y = find(y)
	parent[parent_y] = parent_x

parent = [i for i in range(m+1)]

def job_sequencing(jobs):
	global parent 
	n = len(jobs)

	total_rewards = 0
	for job in jobs:
		available_slot = find(job[0])
		if available_slot > 0:
			union(available_slot-1, available_slot)
			total_rewards += job[1]
	return total_rewards
print(job_sequencing(jobs))

Submission Info

Submission Time
Task D - Summer Vacation
User pyduper
Language Python (3.4.3)
Score 400
Code Size 785 Byte
Status AC
Exec Time 632 ms
Memory 30812 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 21
AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 18 ms 3064 KB
sample_02 AC 18 ms 3064 KB
sample_03 AC 18 ms 3064 KB
testcase_01 AC 80 ms 7252 KB
testcase_02 AC 31 ms 4784 KB
testcase_03 AC 297 ms 9544 KB
testcase_04 AC 585 ms 30700 KB
testcase_05 AC 586 ms 30812 KB
testcase_06 AC 287 ms 4656 KB
testcase_07 AC 570 ms 30748 KB
testcase_08 AC 190 ms 11356 KB
testcase_09 AC 402 ms 21596 KB
testcase_10 AC 599 ms 30748 KB
testcase_11 AC 532 ms 27956 KB
testcase_12 AC 147 ms 9972 KB
testcase_13 AC 580 ms 30716 KB
testcase_14 AC 452 ms 22756 KB
testcase_15 AC 52 ms 4700 KB
testcase_16 AC 489 ms 24504 KB
testcase_17 AC 101 ms 7144 KB
testcase_18 AC 632 ms 30496 KB