208732026-01-10 18:01:42vyrallMunkákpython3Elfogadva 80/80414ms18256 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]
        else:
            dp[1] = megbizasok[1][0]
    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 >= 0:
    if j == 0:
        if dp[0] > 0:
            dolgozott[0] = True
        break
    elif j == 1:
        if dp[1] == megbizasok[1][0] and megbizasok[1][0] > 0:
            dolgozott[1] = True
        elif dp[1] == dp[0] and dp[0] > 0:
            dolgozott[0] = True
        break
    else:
        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
1Elfogadva16ms3128 KiB
2Elfogadva234ms5428 KiB
subtask210/10
3Elfogadva16ms3124 KiB
4Elfogadva16ms3016 KiB
5Elfogadva16ms3124 KiB
6Elfogadva16ms3124 KiB
7Elfogadva17ms3320 KiB
subtask310/10
8Elfogadva16ms3264 KiB
9Elfogadva16ms3124 KiB
10Elfogadva16ms3124 KiB
11Elfogadva16ms3112 KiB
12Elfogadva16ms3208 KiB
subtask410/10
13Elfogadva16ms3124 KiB
14Elfogadva16ms3016 KiB
15Elfogadva16ms3124 KiB
16Elfogadva16ms3124 KiB
17Elfogadva17ms3320 KiB
18Elfogadva17ms3120 KiB
19Elfogadva16ms3152 KiB
20Elfogadva17ms3252 KiB
21Elfogadva16ms3028 KiB
22Elfogadva17ms3312 KiB
subtask510/10
23Elfogadva16ms3264 KiB
24Elfogadva16ms3124 KiB
25Elfogadva16ms3124 KiB
26Elfogadva16ms3112 KiB
27Elfogadva16ms3208 KiB
28Elfogadva21ms3528 KiB
29Elfogadva21ms3436 KiB
30Elfogadva24ms3308 KiB
31Elfogadva24ms3380 KiB
32Elfogadva26ms3380 KiB
subtask610/10
33Elfogadva16ms3124 KiB
34Elfogadva16ms3016 KiB
35Elfogadva16ms3124 KiB
36Elfogadva16ms3124 KiB
37Elfogadva17ms3320 KiB
38Elfogadva16ms3264 KiB
39Elfogadva16ms3124 KiB
40Elfogadva16ms3124 KiB
41Elfogadva16ms3112 KiB
42Elfogadva16ms3208 KiB
43Elfogadva17ms3120 KiB
44Elfogadva16ms3152 KiB
45Elfogadva17ms3252 KiB
46Elfogadva16ms3028 KiB
47Elfogadva17ms3312 KiB
48Elfogadva21ms3528 KiB
49Elfogadva21ms3436 KiB
50Elfogadva24ms3308 KiB
51Elfogadva24ms3380 KiB
52Elfogadva26ms3380 KiB
53Elfogadva27ms3312 KiB
54Elfogadva27ms3380 KiB
55Elfogadva26ms3380 KiB
56Elfogadva27ms3576 KiB
57Elfogadva28ms3576 KiB
subtask710/10
58Elfogadva16ms3124 KiB
59Elfogadva16ms3016 KiB
60Elfogadva16ms3124 KiB
61Elfogadva16ms3124 KiB
62Elfogadva17ms3320 KiB
63Elfogadva16ms3264 KiB
64Elfogadva16ms3124 KiB
65Elfogadva16ms3124 KiB
66Elfogadva16ms3112 KiB
67Elfogadva16ms3208 KiB
68Elfogadva17ms3120 KiB
69Elfogadva16ms3152 KiB
70Elfogadva17ms3252 KiB
71Elfogadva16ms3028 KiB
72Elfogadva17ms3312 KiB
73Elfogadva21ms3528 KiB
74Elfogadva21ms3436 KiB
75Elfogadva24ms3308 KiB
76Elfogadva24ms3380 KiB
77Elfogadva26ms3380 KiB
78Elfogadva27ms3312 KiB
79Elfogadva27ms3380 KiB
80Elfogadva26ms3380 KiB
81Elfogadva27ms3576 KiB
82Elfogadva28ms3576 KiB
83Elfogadva195ms10788 KiB
84Elfogadva195ms10800 KiB
85Elfogadva186ms10700 KiB
86Elfogadva192ms10672 KiB
87Elfogadva188ms11060 KiB
subtask820/20
88Elfogadva16ms3124 KiB
89Elfogadva16ms3016 KiB
90Elfogadva16ms3124 KiB
91Elfogadva16ms3124 KiB
92Elfogadva17ms3320 KiB
93Elfogadva16ms3264 KiB
94Elfogadva16ms3124 KiB
95Elfogadva16ms3124 KiB
96Elfogadva16ms3112 KiB
97Elfogadva16ms3208 KiB
98Elfogadva17ms3120 KiB
99Elfogadva16ms3152 KiB
100Elfogadva17ms3252 KiB
101Elfogadva16ms3028 KiB
102Elfogadva17ms3312 KiB
103Elfogadva21ms3528 KiB
104Elfogadva21ms3436 KiB
105Elfogadva24ms3308 KiB
106Elfogadva24ms3380 KiB
107Elfogadva26ms3380 KiB
108Elfogadva27ms3312 KiB
109Elfogadva27ms3380 KiB
110Elfogadva26ms3380 KiB
111Elfogadva27ms3576 KiB
112Elfogadva28ms3576 KiB
113Elfogadva195ms10788 KiB
114Elfogadva195ms10800 KiB
115Elfogadva186ms10700 KiB
116Elfogadva192ms10672 KiB
117Elfogadva188ms11060 KiB
118Elfogadva405ms18164 KiB
119Elfogadva414ms18164 KiB
120Elfogadva386ms18244 KiB
121Elfogadva375ms18160 KiB
122Elfogadva407ms18168 KiB
123Elfogadva404ms18028 KiB
124Elfogadva386ms18160 KiB
125Elfogadva368ms18256 KiB
126Elfogadva375ms18168 KiB
127Elfogadva370ms18168 KiB