185462025-10-26 14:11:17szabelrMunkákcpp17Elfogadva 80/80174ms7496 KiB
// Munkak.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int best[100001]{ 0 };
vector<int>v;

struct Munka {
	int penz;
	int kod;
};
int main()
{
	int n, m,x,y,jok;
	cin >> n >> m;
	map<int, Munka> munkak;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		if (y > munkak[x].penz)
		{
			munkak[x].penz = y;
			munkak[x].kod = i;
		}
		
	}
	best[1] = munkak[1].penz;
	for (int i = 2; i <= n; i++)
	{
		if (munkak[i].penz != 0) {
			if (best[i - 2] + munkak[i].penz > best[i - 1]) {
				best[i] = best[i - 2] + munkak[i].penz;

			}
				
			
			else {
				best[i] = best[i - 1];
			}
								
		}else
			best[i] = best[i - 1];
	}
	int i = n;
	while (i >= 1)
	{
		if (best[i] == best[i - 1])
			i--;
		else
		{
			v.push_back(i);
			i = i - 2;
		}
	}
	cout << best[n] << " "<<v.size()<<endl;
	for (int i = 0; i <= v.size()-1; i++) {
		cout << munkak[v[i]].kod<<" ";
	}

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva87ms996 KiB
subtask210/10
3Elfogadva1ms500 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms500 KiB
subtask310/10
8Elfogadva1ms500 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
subtask410/10
13Elfogadva1ms500 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms500 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
22Elfogadva1ms316 KiB
subtask510/10
23Elfogadva1ms500 KiB
24Elfogadva1ms316 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva2ms564 KiB
29Elfogadva2ms564 KiB
30Elfogadva2ms820 KiB
31Elfogadva3ms820 KiB
32Elfogadva3ms820 KiB
subtask610/10
33Elfogadva1ms500 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms500 KiB
38Elfogadva1ms500 KiB
39Elfogadva1ms316 KiB
40Elfogadva1ms316 KiB
41Elfogadva1ms316 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva1ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva1ms316 KiB
48Elfogadva2ms564 KiB
49Elfogadva2ms564 KiB
50Elfogadva2ms820 KiB
51Elfogadva3ms820 KiB
52Elfogadva3ms820 KiB
53Elfogadva3ms1268 KiB
54Elfogadva3ms1076 KiB
55Elfogadva3ms1264 KiB
56Elfogadva3ms1076 KiB
57Elfogadva3ms940 KiB
subtask710/10
58Elfogadva1ms500 KiB
59Elfogadva1ms316 KiB
60Elfogadva1ms316 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms500 KiB
63Elfogadva1ms500 KiB
64Elfogadva1ms316 KiB
65Elfogadva1ms316 KiB
66Elfogadva1ms316 KiB
67Elfogadva1ms316 KiB
68Elfogadva1ms316 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva2ms564 KiB
74Elfogadva2ms564 KiB
75Elfogadva2ms820 KiB
76Elfogadva3ms820 KiB
77Elfogadva3ms820 KiB
78Elfogadva3ms1268 KiB
79Elfogadva3ms1076 KiB
80Elfogadva3ms1264 KiB
81Elfogadva3ms1076 KiB
82Elfogadva3ms940 KiB
83Elfogadva79ms3848 KiB
84Elfogadva81ms3892 KiB
85Elfogadva79ms3892 KiB
86Elfogadva79ms4012 KiB
87Elfogadva79ms4012 KiB
subtask820/20
88Elfogadva1ms500 KiB
89Elfogadva1ms316 KiB
90Elfogadva1ms316 KiB
91Elfogadva1ms316 KiB
92Elfogadva1ms500 KiB
93Elfogadva1ms500 KiB
94Elfogadva1ms316 KiB
95Elfogadva1ms316 KiB
96Elfogadva1ms316 KiB
97Elfogadva1ms316 KiB
98Elfogadva1ms316 KiB
99Elfogadva1ms316 KiB
100Elfogadva1ms316 KiB
101Elfogadva1ms316 KiB
102Elfogadva1ms316 KiB
103Elfogadva2ms564 KiB
104Elfogadva2ms564 KiB
105Elfogadva2ms820 KiB
106Elfogadva3ms820 KiB
107Elfogadva3ms820 KiB
108Elfogadva3ms1268 KiB
109Elfogadva3ms1076 KiB
110Elfogadva3ms1264 KiB
111Elfogadva3ms1076 KiB
112Elfogadva3ms940 KiB
113Elfogadva79ms3848 KiB
114Elfogadva81ms3892 KiB
115Elfogadva79ms3892 KiB
116Elfogadva79ms4012 KiB
117Elfogadva79ms4012 KiB
118Elfogadva174ms7348 KiB
119Elfogadva174ms7396 KiB
120Elfogadva165ms7340 KiB
121Elfogadva165ms7344 KiB
122Elfogadva168ms7344 KiB
123Elfogadva166ms7336 KiB
124Elfogadva164ms7496 KiB
125Elfogadva164ms7452 KiB
126Elfogadva162ms7344 KiB
127Elfogadva167ms7348 KiB