208662026-01-10 17:13:20vyrallMunkákpython3Partially correct 12/80428ms17736 KiB

n, m = map(int, input().split())
megbizasok = m * [(0, 0)]
dolgozott = m * [False]
for i in range(m):
    nap, penz = map(int, input().split())
    megbizasok[nap - 1] = (max(megbizasok[nap - 1][0], penz), i + 1)

dp = m * [0]
dp[0] = megbizasok[0][0]
for i in range(1, m):
    if i == 1:
        if dp[0] > megbizasok[1][0]:
            dp[1] = dp[0]
            dolgozott[0] =  True
        else:
            dp[1] = megbizasok[1][0]
    else:
        if megbizasok[i][0] != 0:
            if dp[i - 1] >= dp[i - 2] + megbizasok[i][0]:
                dp[i] = dp[i - 1]
                dolgozott[i] = False
            else:
                dp[i] = dp[i - 2] + megbizasok[i][0]
                dolgozott[i - 1] = False
                dolgozott[i] = True
        else:
            dp[i] = dp[i-1]
            dolgozott[i] = False

print(dp[-1], dolgozott.count(True))
ids = []
for i in range(m):
    if dolgozott[i]:
        ids.append(megbizasok[i][1])
print(' '.join(map(str, ids)))
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted16ms3224 KiB
2Partially correct310ms7104 KiB
subtask26/10
3Partially correct17ms3084 KiB
4Partially correct17ms3108 KiB
5Partially correct16ms3124 KiB
6Partially correct16ms3068 KiB
7Partially correct16ms3124 KiB
subtask30/10
8Runtime error17ms3124 KiB
9Runtime error16ms3104 KiB
10Runtime error17ms3124 KiB
11Runtime error17ms3360 KiB
12Runtime error17ms3144 KiB
subtask46/10
13Partially correct17ms3084 KiB
14Partially correct17ms3108 KiB
15Partially correct16ms3124 KiB
16Partially correct16ms3068 KiB
17Partially correct16ms3124 KiB
18Partially correct16ms3124 KiB
19Partially correct16ms3116 KiB
20Partially correct16ms3124 KiB
21Partially correct17ms3144 KiB
22Partially correct16ms3124 KiB
subtask50/10
23Runtime error17ms3124 KiB
24Runtime error16ms3104 KiB
25Runtime error17ms3124 KiB
26Runtime error17ms3360 KiB
27Runtime error17ms3144 KiB
28Runtime error17ms3124 KiB
29Runtime error17ms3116 KiB
30Runtime error16ms3328 KiB
31Runtime error16ms3124 KiB
32Runtime error16ms3124 KiB
subtask60/10
33Partially correct17ms3084 KiB
34Partially correct17ms3108 KiB
35Partially correct16ms3124 KiB
36Partially correct16ms3068 KiB
37Partially correct16ms3124 KiB
38Runtime error17ms3124 KiB
39Runtime error16ms3104 KiB
40Runtime error17ms3124 KiB
41Runtime error17ms3360 KiB
42Runtime error17ms3144 KiB
43Partially correct16ms3124 KiB
44Partially correct16ms3116 KiB
45Partially correct16ms3124 KiB
46Partially correct17ms3144 KiB
47Partially correct16ms3124 KiB
48Runtime error17ms3124 KiB
49Runtime error17ms3116 KiB
50Runtime error16ms3328 KiB
51Runtime error16ms3124 KiB
52Runtime error16ms3124 KiB
53Runtime error17ms3124 KiB
54Runtime error17ms3116 KiB
55Runtime error17ms3116 KiB
56Runtime error16ms3144 KiB
57Runtime error16ms3184 KiB
subtask70/10
58Partially correct17ms3084 KiB
59Partially correct17ms3108 KiB
60Partially correct16ms3124 KiB
61Partially correct16ms3068 KiB
62Partially correct16ms3124 KiB
63Runtime error17ms3124 KiB
64Runtime error16ms3104 KiB
65Runtime error17ms3124 KiB
66Runtime error17ms3360 KiB
67Runtime error17ms3144 KiB
68Partially correct16ms3124 KiB
69Partially correct16ms3116 KiB
70Partially correct16ms3124 KiB
71Partially correct17ms3144 KiB
72Partially correct16ms3124 KiB
73Runtime error17ms3124 KiB
74Runtime error17ms3116 KiB
75Runtime error16ms3328 KiB
76Runtime error16ms3124 KiB
77Runtime error16ms3124 KiB
78Runtime error17ms3124 KiB
79Runtime error17ms3116 KiB
80Runtime error17ms3116 KiB
81Runtime error16ms3144 KiB
82Runtime error16ms3184 KiB
83Partially correct214ms10280 KiB
84Partially correct187ms10308 KiB
85Partially correct194ms10548 KiB
86Partially correct203ms10548 KiB
87Partially correct203ms10292 KiB
subtask80/20
88Partially correct17ms3084 KiB
89Partially correct17ms3108 KiB
90Partially correct16ms3124 KiB
91Partially correct16ms3068 KiB
92Partially correct16ms3124 KiB
93Runtime error17ms3124 KiB
94Runtime error16ms3104 KiB
95Runtime error17ms3124 KiB
96Runtime error17ms3360 KiB
97Runtime error17ms3144 KiB
98Partially correct16ms3124 KiB
99Partially correct16ms3116 KiB
100Partially correct16ms3124 KiB
101Partially correct17ms3144 KiB
102Partially correct16ms3124 KiB
103Runtime error17ms3124 KiB
104Runtime error17ms3116 KiB
105Runtime error16ms3328 KiB
106Runtime error16ms3124 KiB
107Runtime error16ms3124 KiB
108Runtime error17ms3124 KiB
109Runtime error17ms3116 KiB
110Runtime error17ms3116 KiB
111Runtime error16ms3144 KiB
112Runtime error16ms3184 KiB
113Partially correct214ms10280 KiB
114Partially correct187ms10308 KiB
115Partially correct194ms10548 KiB
116Partially correct203ms10548 KiB
117Partially correct203ms10292 KiB
118Partially correct377ms17624 KiB
119Partially correct428ms17736 KiB
120Partially correct419ms17636 KiB
121Partially correct365ms17596 KiB
122Partially correct386ms17632 KiB
123Partially correct414ms17628 KiB
124Partially correct372ms17640 KiB
125Partially correct377ms17632 KiB
126Partially correct405ms17732 KiB
127Partially correct391ms17632 KiB