208712026-01-10 17:53:41vyrallMunkákpython3Részben helyes 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)))
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva16ms3324 KiB
2Részben helyes228ms5176 KiB
subtask210/10
3Elfogadva17ms3112 KiB
4Elfogadva17ms3124 KiB
5Elfogadva17ms3124 KiB
6Elfogadva17ms3184 KiB
7Elfogadva17ms3012 KiB
subtask36/10
8Elfogadva16ms3320 KiB
9Részben helyes16ms3084 KiB
10Elfogadva16ms3124 KiB
11Részben helyes17ms3020 KiB
12Részben helyes17ms3248 KiB
subtask46/10
13Elfogadva17ms3112 KiB
14Elfogadva17ms3124 KiB
15Elfogadva17ms3124 KiB
16Elfogadva17ms3184 KiB
17Elfogadva17ms3012 KiB
18Elfogadva16ms3136 KiB
19Elfogadva16ms3316 KiB
20Részben helyes17ms3104 KiB
21Elfogadva17ms3124 KiB
22Elfogadva17ms2988 KiB
subtask56/10
23Elfogadva16ms3320 KiB
24Részben helyes16ms3084 KiB
25Elfogadva16ms3124 KiB
26Részben helyes17ms3020 KiB
27Részben helyes17ms3248 KiB
28Részben helyes20ms3308 KiB
29Részben helyes21ms3124 KiB
30Részben helyes24ms3332 KiB
31Részben helyes24ms3296 KiB
32Részben helyes26ms3244 KiB
subtask66/10
33Elfogadva17ms3112 KiB
34Elfogadva17ms3124 KiB
35Elfogadva17ms3124 KiB
36Elfogadva17ms3184 KiB
37Elfogadva17ms3012 KiB
38Elfogadva16ms3320 KiB
39Részben helyes16ms3084 KiB
40Elfogadva16ms3124 KiB
41Részben helyes17ms3020 KiB
42Részben helyes17ms3248 KiB
43Elfogadva16ms3136 KiB
44Elfogadva16ms3316 KiB
45Részben helyes17ms3104 KiB
46Elfogadva17ms3124 KiB
47Elfogadva17ms2988 KiB
48Részben helyes20ms3308 KiB
49Részben helyes21ms3124 KiB
50Részben helyes24ms3332 KiB
51Részben helyes24ms3296 KiB
52Részben helyes26ms3244 KiB
53Részben helyes26ms3392 KiB
54Részben helyes27ms3344 KiB
55Részben helyes26ms3368 KiB
56Részben helyes28ms3376 KiB
57Részben helyes25ms3444 KiB
subtask76/10
58Elfogadva17ms3112 KiB
59Elfogadva17ms3124 KiB
60Elfogadva17ms3124 KiB
61Elfogadva17ms3184 KiB
62Elfogadva17ms3012 KiB
63Elfogadva16ms3320 KiB
64Részben helyes16ms3084 KiB
65Elfogadva16ms3124 KiB
66Részben helyes17ms3020 KiB
67Részben helyes17ms3248 KiB
68Elfogadva16ms3136 KiB
69Elfogadva16ms3316 KiB
70Részben helyes17ms3104 KiB
71Elfogadva17ms3124 KiB
72Elfogadva17ms2988 KiB
73Részben helyes20ms3308 KiB
74Részben helyes21ms3124 KiB
75Részben helyes24ms3332 KiB
76Részben helyes24ms3296 KiB
77Részben helyes26ms3244 KiB
78Részben helyes26ms3392 KiB
79Részben helyes27ms3344 KiB
80Részben helyes26ms3368 KiB
81Részben helyes28ms3376 KiB
82Részben helyes25ms3444 KiB
83Elfogadva206ms10776 KiB
84Részben helyes189ms10544 KiB
85Elfogadva192ms11060 KiB
86Elfogadva185ms10660 KiB
87Elfogadva182ms10568 KiB
subtask812/20
88Elfogadva17ms3112 KiB
89Elfogadva17ms3124 KiB
90Elfogadva17ms3124 KiB
91Elfogadva17ms3184 KiB
92Elfogadva17ms3012 KiB
93Elfogadva16ms3320 KiB
94Részben helyes16ms3084 KiB
95Elfogadva16ms3124 KiB
96Részben helyes17ms3020 KiB
97Részben helyes17ms3248 KiB
98Elfogadva16ms3136 KiB
99Elfogadva16ms3316 KiB
100Részben helyes17ms3104 KiB
101Elfogadva17ms3124 KiB
102Elfogadva17ms2988 KiB
103Részben helyes20ms3308 KiB
104Részben helyes21ms3124 KiB
105Részben helyes24ms3332 KiB
106Részben helyes24ms3296 KiB
107Részben helyes26ms3244 KiB
108Részben helyes26ms3392 KiB
109Részben helyes27ms3344 KiB
110Részben helyes26ms3368 KiB
111Részben helyes28ms3376 KiB
112Részben helyes25ms3444 KiB
113Elfogadva206ms10776 KiB
114Részben helyes189ms10544 KiB
115Elfogadva192ms11060 KiB
116Elfogadva185ms10660 KiB
117Elfogadva182ms10568 KiB
118Elfogadva384ms18328 KiB
119Elfogadva375ms18156 KiB
120Részben helyes411ms18340 KiB
121Részben helyes400ms18188 KiB
122Elfogadva395ms18308 KiB
123Részben helyes370ms18140 KiB
124Részben helyes402ms18140 KiB
125Elfogadva372ms18304 KiB
126Elfogadva368ms18148 KiB
127Elfogadva361ms18084 KiB