208692026-01-10 17:31:06vyrallMunkákpython3Partially correct 52/80391ms17792 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]
            dolgozott[i] = False
        else:
            dp[i] = dp[i - 2] + megbizasok[i][0]
            dolgozott[i - 1] = False
            dolgozott[i] = True

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
1Accepted16ms3124 KiB
2Partially correct222ms4916 KiB
subtask210/10
3Accepted16ms3320 KiB
4Accepted17ms3124 KiB
5Accepted17ms2984 KiB
6Accepted16ms3312 KiB
7Accepted17ms3076 KiB
subtask36/10
8Accepted16ms3136 KiB
9Partially correct16ms3124 KiB
10Partially correct16ms3124 KiB
11Partially correct16ms3124 KiB
12Partially correct16ms2992 KiB
subtask46/10
13Accepted16ms3320 KiB
14Accepted17ms3124 KiB
15Accepted17ms2984 KiB
16Accepted16ms3312 KiB
17Accepted17ms3076 KiB
18Partially correct16ms3056 KiB
19Partially correct16ms3124 KiB
20Partially correct16ms3172 KiB
21Partially correct16ms3092 KiB
22Partially correct17ms3148 KiB
subtask56/10
23Accepted16ms3136 KiB
24Partially correct16ms3124 KiB
25Partially correct16ms3124 KiB
26Partially correct16ms3124 KiB
27Partially correct16ms2992 KiB
28Partially correct18ms3320 KiB
29Partially correct18ms3124 KiB
30Partially correct19ms3124 KiB
31Partially correct20ms3296 KiB
32Partially correct20ms3420 KiB
subtask66/10
33Accepted16ms3320 KiB
34Accepted17ms3124 KiB
35Accepted17ms2984 KiB
36Accepted16ms3312 KiB
37Accepted17ms3076 KiB
38Accepted16ms3136 KiB
39Partially correct16ms3124 KiB
40Partially correct16ms3124 KiB
41Partially correct16ms3124 KiB
42Partially correct16ms2992 KiB
43Partially correct16ms3056 KiB
44Partially correct16ms3124 KiB
45Partially correct16ms3172 KiB
46Partially correct16ms3092 KiB
47Partially correct17ms3148 KiB
48Partially correct18ms3320 KiB
49Partially correct18ms3124 KiB
50Partially correct19ms3124 KiB
51Partially correct20ms3296 KiB
52Partially correct20ms3420 KiB
53Partially correct23ms3368 KiB
54Partially correct21ms3628 KiB
55Partially correct24ms3416 KiB
56Partially correct23ms3312 KiB
57Partially correct21ms3428 KiB
subtask76/10
58Accepted16ms3320 KiB
59Accepted17ms3124 KiB
60Accepted17ms2984 KiB
61Accepted16ms3312 KiB
62Accepted17ms3076 KiB
63Accepted16ms3136 KiB
64Partially correct16ms3124 KiB
65Partially correct16ms3124 KiB
66Partially correct16ms3124 KiB
67Partially correct16ms2992 KiB
68Partially correct16ms3056 KiB
69Partially correct16ms3124 KiB
70Partially correct16ms3172 KiB
71Partially correct16ms3092 KiB
72Partially correct17ms3148 KiB
73Partially correct18ms3320 KiB
74Partially correct18ms3124 KiB
75Partially correct19ms3124 KiB
76Partially correct20ms3296 KiB
77Partially correct20ms3420 KiB
78Partially correct23ms3368 KiB
79Partially correct21ms3628 KiB
80Partially correct24ms3416 KiB
81Partially correct23ms3312 KiB
82Partially correct21ms3428 KiB
83Partially correct194ms10288 KiB
84Partially correct173ms10396 KiB
85Partially correct175ms10312 KiB
86Partially correct179ms10544 KiB
87Partially correct172ms10424 KiB
subtask812/20
88Accepted16ms3320 KiB
89Accepted17ms3124 KiB
90Accepted17ms2984 KiB
91Accepted16ms3312 KiB
92Accepted17ms3076 KiB
93Accepted16ms3136 KiB
94Partially correct16ms3124 KiB
95Partially correct16ms3124 KiB
96Partially correct16ms3124 KiB
97Partially correct16ms2992 KiB
98Partially correct16ms3056 KiB
99Partially correct16ms3124 KiB
100Partially correct16ms3172 KiB
101Partially correct16ms3092 KiB
102Partially correct17ms3148 KiB
103Partially correct18ms3320 KiB
104Partially correct18ms3124 KiB
105Partially correct19ms3124 KiB
106Partially correct20ms3296 KiB
107Partially correct20ms3420 KiB
108Partially correct23ms3368 KiB
109Partially correct21ms3628 KiB
110Partially correct24ms3416 KiB
111Partially correct23ms3312 KiB
112Partially correct21ms3428 KiB
113Partially correct194ms10288 KiB
114Partially correct173ms10396 KiB
115Partially correct175ms10312 KiB
116Partially correct179ms10544 KiB
117Partially correct172ms10424 KiB
118Partially correct363ms17600 KiB
119Partially correct354ms17792 KiB
120Partially correct349ms17592 KiB
121Partially correct372ms17700 KiB
122Partially correct347ms17696 KiB
123Partially correct391ms17688 KiB
124Partially correct361ms17680 KiB
125Partially correct345ms17576 KiB
126Partially correct351ms17604 KiB
127Partially correct347ms17604 KiB