196182025-12-17 11:16:14szabel26Munkákcpp17Időlimit túllépés 0/80699ms9244 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)
{
    for (auto& e : napok[akt])
    {
        ossz += e.penz;
        sol.push_back(e);
        if (akt != n && akt != n - 1)
        {
            for (int i = akt + 2; i <= n; ++i)
            {
                if (!napok[i].empty()) backtrack(i, ossz);
            }
        }
        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);
    
    /*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
1Elfogadva2ms316 KiB
2Időlimit túllépés686ms2612 KiB
subtask20/10
3Hibás válasz1ms316 KiB
4Hibás válasz2ms316 KiB
5Hibás válasz1ms508 KiB
6Hibás válasz2ms316 KiB
7Hibás válasz6ms400 KiB
subtask30/10
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
10Részben helyes1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
subtask40/10
13Hibás válasz1ms316 KiB
14Hibás válasz2ms316 KiB
15Hibás válasz1ms508 KiB
16Hibás válasz2ms316 KiB
17Hibás válasz6ms400 KiB
18Hibás válasz1ms316 KiB
19Hibás válasz2ms500 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz7ms400 KiB
22Hibás válasz6ms508 KiB
subtask50/10
23Hibás válasz1ms316 KiB
24Hibás válasz1ms316 KiB
25Részben helyes1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva2ms500 KiB
29Elfogadva4ms316 KiB
30Elfogadva3ms564 KiB
31Elfogadva3ms564 KiB
32Elfogadva3ms564 KiB
subtask60/10
33Hibás válasz1ms316 KiB
34Hibás válasz2ms316 KiB
35Hibás válasz1ms508 KiB
36Hibás válasz2ms316 KiB
37Hibás válasz6ms400 KiB
38Hibás válasz1ms316 KiB
39Hibás válasz1ms316 KiB
40Részben helyes1ms316 KiB
41Elfogadva1ms316 KiB
42Elfogadva1ms316 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz2ms500 KiB
45Hibás válasz1ms316 KiB
46Hibás válasz7ms400 KiB
47Hibás válasz6ms508 KiB
48Elfogadva2ms500 KiB
49Elfogadva4ms316 KiB
50Elfogadva3ms564 KiB
51Elfogadva3ms564 KiB
52Elfogadva3ms564 KiB
53Időlimit túllépés699ms564 KiB
54Időlimit túllépés699ms564 KiB
55Időlimit túllépés699ms564 KiB
56Időlimit túllépés699ms564 KiB
57Időlimit túllépés671ms564 KiB
subtask70/10
58Hibás válasz1ms316 KiB
59Hibás válasz2ms316 KiB
60Hibás válasz1ms508 KiB
61Hibás válasz2ms316 KiB
62Hibás válasz6ms400 KiB
63Hibás válasz1ms316 KiB
64Hibás válasz1ms316 KiB
65Részben helyes1ms316 KiB
66Elfogadva1ms316 KiB
67Elfogadva1ms316 KiB
68Hibás válasz1ms316 KiB
69Hibás válasz2ms500 KiB
70Hibás válasz1ms316 KiB
71Hibás válasz7ms400 KiB
72Hibás válasz6ms508 KiB
73Elfogadva2ms500 KiB
74Elfogadva4ms316 KiB
75Elfogadva3ms564 KiB
76Elfogadva3ms564 KiB
77Elfogadva3ms564 KiB
78Időlimit túllépés699ms564 KiB
79Időlimit túllépés699ms564 KiB
80Időlimit túllépés699ms564 KiB
81Időlimit túllépés699ms564 KiB
82Időlimit túllépés671ms564 KiB
83Időlimit túllépés680ms4784 KiB
84Időlimit túllépés680ms4784 KiB
85Időlimit túllépés680ms4784 KiB
86Időlimit túllépés680ms4784 KiB
87Időlimit túllépés680ms4800 KiB
subtask80/20
88Hibás válasz1ms316 KiB
89Hibás válasz2ms316 KiB
90Hibás válasz1ms508 KiB
91Hibás válasz2ms316 KiB
92Hibás válasz6ms400 KiB
93Hibás válasz1ms316 KiB
94Hibás válasz1ms316 KiB
95Részben helyes1ms316 KiB
96Elfogadva1ms316 KiB
97Elfogadva1ms316 KiB
98Hibás válasz1ms316 KiB
99Hibás válasz2ms500 KiB
100Hibás válasz1ms316 KiB
101Hibás válasz7ms400 KiB
102Hibás válasz6ms508 KiB
103Elfogadva2ms500 KiB
104Elfogadva4ms316 KiB
105Elfogadva3ms564 KiB
106Elfogadva3ms564 KiB
107Elfogadva3ms564 KiB
108Időlimit túllépés699ms564 KiB
109Időlimit túllépés699ms564 KiB
110Időlimit túllépés699ms564 KiB
111Időlimit túllépés699ms564 KiB
112Időlimit túllépés671ms564 KiB
113Időlimit túllépés680ms4784 KiB
114Időlimit túllépés680ms4784 KiB
115Időlimit túllépés680ms4784 KiB
116Időlimit túllépés680ms4784 KiB
117Időlimit túllépés680ms4800 KiB
118Időlimit túllépés686ms9132 KiB
119Időlimit túllépés688ms9148 KiB
120Időlimit túllépés688ms9132 KiB
121Időlimit túllépés688ms9132 KiB
122Időlimit túllépés688ms9144 KiB
123Időlimit túllépés688ms9132 KiB
124Időlimit túllépés689ms9132 KiB
125Időlimit túllépés689ms9180 KiB
126Időlimit túllépés689ms9244 KiB
127Időlimit túllépés689ms9132 KiB