196192025-12-17 11:19:10szabel26Munkákcpp17Időlimit túllépés 0/80689ms9244 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);
        if (a > maxi) maxi = a;
    }

    n = maxi;
    napok.resize(n + 1);
    maxi = 0;

    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
1Elfogadva1ms316 KiB
2Időlimit túllépés685ms2612 KiB
subtask20/10
3Hibás válasz2ms316 KiB
4Hibás válasz1ms316 KiB
5Hibás válasz2ms316 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
11Elfogadva1ms380 KiB
12Elfogadva1ms508 KiB
subtask40/10
13Hibás válasz2ms316 KiB
14Hibás válasz1ms316 KiB
15Hibás válasz2ms316 KiB
16Hibás válasz2ms316 KiB
17Hibás válasz6ms316 KiB
18Hibás válasz1ms316 KiB
19Hibás válasz1ms316 KiB
20Hibás válasz1ms316 KiB
21Hibás válasz6ms316 KiB
22Hibás válasz6ms500 KiB
subtask50/10
23Hibás válasz1ms316 KiB
24Hibás válasz1ms316 KiB
25Részben helyes1ms316 KiB
26Elfogadva1ms380 KiB
27Elfogadva1ms508 KiB
28Elfogadva2ms324 KiB
29Elfogadva2ms564 KiB
30Elfogadva2ms564 KiB
31Elfogadva2ms564 KiB
32Elfogadva2ms564 KiB
subtask60/10
33Hibás válasz2ms316 KiB
34Hibás válasz1ms316 KiB
35Hibás válasz2ms316 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
41Elfogadva1ms380 KiB
42Elfogadva1ms508 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz1ms316 KiB
45Hibás válasz1ms316 KiB
46Hibás válasz6ms316 KiB
47Hibás válasz6ms500 KiB
48Elfogadva2ms324 KiB
49Elfogadva2ms564 KiB
50Elfogadva2ms564 KiB
51Elfogadva2ms564 KiB
52Elfogadva2ms564 KiB
53Időlimit túllépés688ms564 KiB
54Időlimit túllépés689ms564 KiB
55Időlimit túllépés688ms564 KiB
56Időlimit túllépés689ms756 KiB
57Időlimit túllépés686ms564 KiB
subtask70/10
58Hibás válasz2ms316 KiB
59Hibás válasz1ms316 KiB
60Hibás válasz2ms316 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
66Elfogadva1ms380 KiB
67Elfogadva1ms508 KiB
68Hibás válasz1ms316 KiB
69Hibás válasz1ms316 KiB
70Hibás válasz1ms316 KiB
71Hibás válasz6ms316 KiB
72Hibás válasz6ms500 KiB
73Elfogadva2ms324 KiB
74Elfogadva2ms564 KiB
75Elfogadva2ms564 KiB
76Elfogadva2ms564 KiB
77Elfogadva2ms564 KiB
78Időlimit túllépés688ms564 KiB
79Időlimit túllépés689ms564 KiB
80Időlimit túllépés688ms564 KiB
81Időlimit túllépés689ms756 KiB
82Időlimit túllépés686ms564 KiB
83Időlimit túllépés683ms4784 KiB
84Időlimit túllépés683ms4784 KiB
85Időlimit túllépés684ms4872 KiB
86Időlimit túllépés683ms4800 KiB
87Időlimit túllépés689ms4828 KiB
subtask80/20
88Hibás válasz2ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz2ms316 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
96Elfogadva1ms380 KiB
97Elfogadva1ms508 KiB
98Hibás válasz1ms316 KiB
99Hibás válasz1ms316 KiB
100Hibás válasz1ms316 KiB
101Hibás válasz6ms316 KiB
102Hibás válasz6ms500 KiB
103Elfogadva2ms324 KiB
104Elfogadva2ms564 KiB
105Elfogadva2ms564 KiB
106Elfogadva2ms564 KiB
107Elfogadva2ms564 KiB
108Időlimit túllépés688ms564 KiB
109Időlimit túllépés689ms564 KiB
110Időlimit túllépés688ms564 KiB
111Időlimit túllépés689ms756 KiB
112Időlimit túllépés686ms564 KiB
113Időlimit túllépés683ms4784 KiB
114Időlimit túllépés683ms4784 KiB
115Időlimit túllépés684ms4872 KiB
116Időlimit túllépés683ms4800 KiB
117Időlimit túllépés689ms4828 KiB
118Időlimit túllépés686ms9132 KiB
119Időlimit túllépés688ms9032 KiB
120Időlimit túllépés686ms9160 KiB
121Időlimit túllépés688ms9104 KiB
122Időlimit túllépés688ms9208 KiB
123Időlimit túllépés688ms9040 KiB
124Időlimit túllépés689ms9132 KiB
125Időlimit túllépés689ms9136 KiB
126Időlimit túllépés683ms9244 KiB
127Időlimit túllépés683ms9136 KiB