197472025-12-21 13:43:00szabel26Munkákcpp17Hibás válasz 22/8082ms2540 KiB
// munkak_2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct adat {
    int sorszam, penz, nap;
};

int hasonlit(adat a, adat b)
{
    return a.penz > b.penz;
}

vector<adat>x;
vector<int>st, sol;

int n, m, i, ossz;

void backtrack(int akt)
{
    sol.push_back(x[akt].sorszam);
    ossz += x[akt].penz;
    st[x[akt].nap] = 1;
    st[x[akt].nap + 1] = 1;
    if (sol.size() <= n / 2)
    {
        int k = akt + 1;
        while (k <= n)
        {
            if (st[x[k].nap] == 0 && st[x[k].nap + 1] == 0)
            {
                backtrack(k);
                return;
            }
            ++k;
        }
    }
}

int main()
{
    cin >> n >> m;

    x.resize(n + 1);
    st.resize(n + 2, 0);
    for (i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        if (x[a].penz < b)
        {
            x[a].sorszam = i;
            x[a].penz = b;
            x[a].nap = a;
        }
    }

    sort(x.begin() + 1, x.end(), hasonlit);

    backtrack(1);

    cout << ossz << " " << sol.size() << endl;
    for (auto& e : sol) cout << e << " ";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Hibás válasz59ms564 KiB
subtask210/10
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask36/10
8Részben helyes1ms316 KiB
9Részben helyes1ms552 KiB
10Elfogadva1ms316 KiB
11Részben helyes1ms316 KiB
12Részben helyes1ms316 KiB
subtask40/10
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Hibás válasz1ms500 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Elfogadva1ms316 KiB
22Hibás válasz1ms316 KiB
subtask56/10
23Részben helyes1ms316 KiB
24Részben helyes1ms552 KiB
25Elfogadva1ms316 KiB
26Részben helyes1ms316 KiB
27Részben helyes1ms316 KiB
28Részben helyes1ms316 KiB
29Részben helyes1ms316 KiB
30Részben helyes1ms316 KiB
31Részben helyes1ms316 KiB
32Részben helyes1ms316 KiB
subtask60/10
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Részben helyes1ms316 KiB
39Részben helyes1ms552 KiB
40Elfogadva1ms316 KiB
41Részben helyes1ms316 KiB
42Részben helyes1ms316 KiB
43Hibás válasz1ms500 KiB
44Hibás válasz1ms316 KiB
45Hibás válasz1ms316 KiB
46Elfogadva1ms316 KiB
47Hibás válasz1ms316 KiB
48Részben helyes1ms316 KiB
49Részben helyes1ms316 KiB
50Részben helyes1ms316 KiB
51Részben helyes1ms316 KiB
52Részben helyes1ms316 KiB
53Részben helyes1ms316 KiB
54Részben helyes1ms316 KiB
55Részben helyes1ms316 KiB
56Részben helyes1ms316 KiB
57Részben helyes1ms316 KiB
subtask70/10
58Elfogadva1ms316 KiB
59Elfogadva1ms316 KiB
60Elfogadva1ms316 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms316 KiB
63Részben helyes1ms316 KiB
64Részben helyes1ms552 KiB
65Elfogadva1ms316 KiB
66Részben helyes1ms316 KiB
67Részben helyes1ms316 KiB
68Hibás válasz1ms500 KiB
69Hibás válasz1ms316 KiB
70Hibás válasz1ms316 KiB
71Elfogadva1ms316 KiB
72Hibás válasz1ms316 KiB
73Részben helyes1ms316 KiB
74Részben helyes1ms316 KiB
75Részben helyes1ms316 KiB
76Részben helyes1ms316 KiB
77Részben helyes1ms316 KiB
78Részben helyes1ms316 KiB
79Részben helyes1ms316 KiB
80Részben helyes1ms316 KiB
81Részben helyes1ms316 KiB
82Részben helyes1ms316 KiB
83Hibás válasz39ms1448 KiB
84Hibás válasz39ms1452 KiB
85Hibás válasz39ms1460 KiB
86Hibás válasz41ms1448 KiB
87Hibás válasz41ms1348 KiB
subtask80/20
88Elfogadva1ms316 KiB
89Elfogadva1ms316 KiB
90Elfogadva1ms316 KiB
91Elfogadva1ms316 KiB
92Elfogadva1ms316 KiB
93Részben helyes1ms316 KiB
94Részben helyes1ms552 KiB
95Elfogadva1ms316 KiB
96Részben helyes1ms316 KiB
97Részben helyes1ms316 KiB
98Hibás válasz1ms500 KiB
99Hibás válasz1ms316 KiB
100Hibás válasz1ms316 KiB
101Elfogadva1ms316 KiB
102Hibás válasz1ms316 KiB
103Részben helyes1ms316 KiB
104Részben helyes1ms316 KiB
105Részben helyes1ms316 KiB
106Részben helyes1ms316 KiB
107Részben helyes1ms316 KiB
108Részben helyes1ms316 KiB
109Részben helyes1ms316 KiB
110Részben helyes1ms316 KiB
111Részben helyes1ms316 KiB
112Részben helyes1ms316 KiB
113Hibás válasz39ms1448 KiB
114Hibás válasz39ms1452 KiB
115Hibás válasz39ms1460 KiB
116Hibás válasz41ms1448 KiB
117Hibás válasz41ms1348 KiB
118Hibás válasz79ms2364 KiB
119Hibás válasz82ms2360 KiB
120Hibás válasz82ms2540 KiB
121Hibás válasz81ms2360 KiB
122Hibás válasz81ms2356 KiB
123Hibás válasz79ms2356 KiB
124Hibás válasz81ms2356 KiB
125Hibás válasz82ms2356 KiB
126Hibás válasz82ms2360 KiB
127Hibás válasz82ms2368 KiB