208712026-01-10 17:53:41vyrallMunkákpython3Partially correct 52/80411ms18340 KiB

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

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

j = n - 1
while j >= 2:
    if dp[j] == dp[j - 2] + megbizasok[j][0] and dp[j] != dp[j - 1]:
        dolgozott[j] = True
        j -= 2
    else:
        j -= 1

print(dp[-1], dolgozott.count(True))
ids = []
for i in range(n):
    if dolgozott[i]:
        ids.append(megbizasok[i][1])
print(' '.join(map(str, ids)))
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted16ms3324 KiB
2Partially correct228ms5176 KiB
subtask210/10
3Accepted17ms3112 KiB
4Accepted17ms3124 KiB
5Accepted17ms3124 KiB
6Accepted17ms3184 KiB
7Accepted17ms3012 KiB
subtask36/10
8Accepted16ms3320 KiB
9Partially correct16ms3084 KiB
10Accepted16ms3124 KiB
11Partially correct17ms3020 KiB
12Partially correct17ms3248 KiB
subtask46/10
13Accepted17ms3112 KiB
14Accepted17ms3124 KiB
15Accepted17ms3124 KiB
16Accepted17ms3184 KiB
17Accepted17ms3012 KiB
18Accepted16ms3136 KiB
19Accepted16ms3316 KiB
20Partially correct17ms3104 KiB
21Accepted17ms3124 KiB
22Accepted17ms2988 KiB
subtask56/10
23Accepted16ms3320 KiB
24Partially correct16ms3084 KiB
25Accepted16ms3124 KiB
26Partially correct17ms3020 KiB
27Partially correct17ms3248 KiB
28Partially correct20ms3308 KiB
29Partially correct21ms3124 KiB
30Partially correct24ms3332 KiB
31Partially correct24ms3296 KiB
32Partially correct26ms3244 KiB
subtask66/10
33Accepted17ms3112 KiB
34Accepted17ms3124 KiB
35Accepted17ms3124 KiB
36Accepted17ms3184 KiB
37Accepted17ms3012 KiB
38Accepted16ms3320 KiB
39Partially correct16ms3084 KiB
40Accepted16ms3124 KiB
41Partially correct17ms3020 KiB
42Partially correct17ms3248 KiB
43Accepted16ms3136 KiB
44Accepted16ms3316 KiB
45Partially correct17ms3104 KiB
46Accepted17ms3124 KiB
47Accepted17ms2988 KiB
48Partially correct20ms3308 KiB
49Partially correct21ms3124 KiB
50Partially correct24ms3332 KiB
51Partially correct24ms3296 KiB
52Partially correct26ms3244 KiB
53Partially correct26ms3392 KiB
54Partially correct27ms3344 KiB
55Partially correct26ms3368 KiB
56Partially correct28ms3376 KiB
57Partially correct25ms3444 KiB
subtask76/10
58Accepted17ms3112 KiB
59Accepted17ms3124 KiB
60Accepted17ms3124 KiB
61Accepted17ms3184 KiB
62Accepted17ms3012 KiB
63Accepted16ms3320 KiB
64Partially correct16ms3084 KiB
65Accepted16ms3124 KiB
66Partially correct17ms3020 KiB
67Partially correct17ms3248 KiB
68Accepted16ms3136 KiB
69Accepted16ms3316 KiB
70Partially correct17ms3104 KiB
71Accepted17ms3124 KiB
72Accepted17ms2988 KiB
73Partially correct20ms3308 KiB
74Partially correct21ms3124 KiB
75Partially correct24ms3332 KiB
76Partially correct24ms3296 KiB
77Partially correct26ms3244 KiB
78Partially correct26ms3392 KiB
79Partially correct27ms3344 KiB
80Partially correct26ms3368 KiB
81Partially correct28ms3376 KiB
82Partially correct25ms3444 KiB
83Accepted206ms10776 KiB
84Partially correct189ms10544 KiB
85Accepted192ms11060 KiB
86Accepted185ms10660 KiB
87Accepted182ms10568 KiB
subtask812/20
88Accepted17ms3112 KiB
89Accepted17ms3124 KiB
90Accepted17ms3124 KiB
91Accepted17ms3184 KiB
92Accepted17ms3012 KiB
93Accepted16ms3320 KiB
94Partially correct16ms3084 KiB
95Accepted16ms3124 KiB
96Partially correct17ms3020 KiB
97Partially correct17ms3248 KiB
98Accepted16ms3136 KiB
99Accepted16ms3316 KiB
100Partially correct17ms3104 KiB
101Accepted17ms3124 KiB
102Accepted17ms2988 KiB
103Partially correct20ms3308 KiB
104Partially correct21ms3124 KiB
105Partially correct24ms3332 KiB
106Partially correct24ms3296 KiB
107Partially correct26ms3244 KiB
108Partially correct26ms3392 KiB
109Partially correct27ms3344 KiB
110Partially correct26ms3368 KiB
111Partially correct28ms3376 KiB
112Partially correct25ms3444 KiB
113Accepted206ms10776 KiB
114Partially correct189ms10544 KiB
115Accepted192ms11060 KiB
116Accepted185ms10660 KiB
117Accepted182ms10568 KiB
118Accepted384ms18328 KiB
119Accepted375ms18156 KiB
120Partially correct411ms18340 KiB
121Partially correct400ms18188 KiB
122Accepted395ms18308 KiB
123Partially correct370ms18140 KiB
124Partially correct402ms18140 KiB
125Accepted372ms18304 KiB
126Accepted368ms18148 KiB
127Accepted361ms18084 KiB