196172025-12-17 11:09:03szabel26Munkákcpp17Időlimit túllépés 0/80690ms9800 KiB
// munkak.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;
};

vector<vector<adat>>napok;
vector<adat>sol;
vector<adat>sol2;

int n, m, maxi = 0;

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

void check(int ossz)
{
    if (ossz >= maxi)
    {
        maxi = ossz;
        sol2 = sol;
        //sol.clear();
    }
}

void backtrack(int akt, int ossz, int lep)
{
    for (auto& e : napok[akt])
    {
        ossz += e.penz;
        sol.push_back(e);
        for (int i = akt + 2; i <= n; ++i)
        {
            if(!napok[i].empty()) backtrack(i, ossz, lep + 1);
        }
        check(ossz);
        if(!sol.empty()) sol.pop_back();
    }
}

int main()
{
    cin >> n >> m;
    napok.resize(n + 1);

    int a;
    adat b;
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b.penz;
        b.sorszam = i;
        napok[a].push_back(b);
        //napok[a + 1].push_back(b);
    }

    for (int i = 1; i <= n; ++i) if(!napok[i].empty()) backtrack(i, 0, 1);
    
    /*for (int i = 1; i <= m; ++i)
    {
        sort(napok[i].begin(), napok[i].end(), hasonlit);
    }*/

    cout << maxi << " " << sol2.size() << endl;
    for (auto& e : sol2)
    {
        cout << e.sorszam << " ";
    }
}

// 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
2Időlimit túllépés679ms2612 KiB
subtask20/10
3Hibás válasz1ms316 KiB
4Hibás válasz1ms316 KiB
5Hibás válasz1ms316 KiB
6Hibás válasz2ms316 KiB
7Hibás válasz6ms316 KiB
subtask30/10
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
10Részben helyes1ms316 KiB
11Elfogadva1ms392 KiB
12Elfogadva1ms316 KiB
subtask40/10
13Hibás válasz1ms316 KiB
14Hibás válasz1ms316 KiB
15Hibás válasz1ms316 KiB
16Hibás válasz2ms316 KiB
17Hibás válasz6ms316 KiB
18Hibás válasz1ms500 KiB
19Hibás válasz1ms508 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz7ms316 KiB
22Hibás válasz6ms400 KiB
subtask50/10
23Hibás válasz1ms316 KiB
24Hibás válasz1ms316 KiB
25Részben helyes1ms316 KiB
26Elfogadva1ms392 KiB
27Elfogadva1ms316 KiB
28Elfogadva1ms512 KiB
29Elfogadva4ms564 KiB
30Elfogadva3ms564 KiB
31Elfogadva3ms760 KiB
32Elfogadva3ms568 KiB
subtask60/10
33Hibás válasz1ms316 KiB
34Hibás válasz1ms316 KiB
35Hibás válasz1ms316 KiB
36Hibás válasz2ms316 KiB
37Hibás válasz6ms316 KiB
38Hibás válasz1ms316 KiB
39Hibás válasz1ms316 KiB
40Részben helyes1ms316 KiB
41Elfogadva1ms392 KiB
42Elfogadva1ms316 KiB
43Hibás válasz1ms500 KiB
44Hibás válasz1ms508 KiB
45Hibás válasz1ms316 KiB
46Hibás válasz7ms316 KiB
47Hibás válasz6ms400 KiB
48Elfogadva1ms512 KiB
49Elfogadva4ms564 KiB
50Elfogadva3ms564 KiB
51Elfogadva3ms760 KiB
52Elfogadva3ms568 KiB
53Időlimit túllépés680ms564 KiB
54Időlimit túllépés680ms564 KiB
55Időlimit túllépés680ms756 KiB
56Időlimit túllépés681ms564 KiB
57Időlimit túllépés675ms756 KiB
subtask70/10
58Hibás válasz1ms316 KiB
59Hibás válasz1ms316 KiB
60Hibás válasz1ms316 KiB
61Hibás válasz2ms316 KiB
62Hibás válasz6ms316 KiB
63Hibás válasz1ms316 KiB
64Hibás válasz1ms316 KiB
65Részben helyes1ms316 KiB
66Elfogadva1ms392 KiB
67Elfogadva1ms316 KiB
68Hibás válasz1ms500 KiB
69Hibás válasz1ms508 KiB
70Hibás válasz1ms316 KiB
71Hibás válasz7ms316 KiB
72Hibás válasz6ms400 KiB
73Elfogadva1ms512 KiB
74Elfogadva4ms564 KiB
75Elfogadva3ms564 KiB
76Elfogadva3ms760 KiB
77Elfogadva3ms568 KiB
78Időlimit túllépés680ms564 KiB
79Időlimit túllépés680ms564 KiB
80Időlimit túllépés680ms756 KiB
81Időlimit túllépés681ms564 KiB
82Időlimit túllépés675ms756 KiB
83Időlimit túllépés680ms4784 KiB
84Időlimit túllépés680ms4900 KiB
85Időlimit túllépés680ms4720 KiB
86Időlimit túllépés680ms4784 KiB
87Időlimit túllépés677ms4784 KiB
subtask80/20
88Hibás válasz1ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Hibás válasz2ms316 KiB
92Hibás válasz6ms316 KiB
93Hibás válasz1ms316 KiB
94Hibás válasz1ms316 KiB
95Részben helyes1ms316 KiB
96Elfogadva1ms392 KiB
97Elfogadva1ms316 KiB
98Hibás válasz1ms500 KiB
99Hibás válasz1ms508 KiB
100Hibás válasz1ms316 KiB
101Hibás válasz7ms316 KiB
102Hibás válasz6ms400 KiB
103Elfogadva1ms512 KiB
104Elfogadva4ms564 KiB
105Elfogadva3ms564 KiB
106Elfogadva3ms760 KiB
107Elfogadva3ms568 KiB
108Időlimit túllépés680ms564 KiB
109Időlimit túllépés680ms564 KiB
110Időlimit túllépés680ms756 KiB
111Időlimit túllépés681ms564 KiB
112Időlimit túllépés675ms756 KiB
113Időlimit túllépés680ms4784 KiB
114Időlimit túllépés680ms4900 KiB
115Időlimit túllépés680ms4720 KiB
116Időlimit túllépés680ms4784 KiB
117Időlimit túllépés677ms4784 KiB
118Időlimit túllépés689ms9136 KiB
119Időlimit túllépés690ms9228 KiB
120Időlimit túllépés689ms9228 KiB
121Időlimit túllépés690ms9168 KiB
122Időlimit túllépés685ms9044 KiB
123Időlimit túllépés686ms9132 KiB
124Időlimit túllépés685ms9140 KiB
125Időlimit túllépés686ms9132 KiB
126Időlimit túllépés666ms9020 KiB
127Időlimit túllépés667ms9800 KiB