197502025-12-21 14:09:41szabel26Munkákcpp17Időlimit túllépés 10/80699ms2684 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, y;
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;
            }
            else y.push_back(x[k]);
            ++k;
        }
    }
}

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

    x.resize(n + 1);
    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);
    for (i = x.size() - 1; i >= 1; --i)
    {
        if (x[i].penz == 0) x.pop_back();
        else break;
    }
    n = x.size() - 1;

    st.resize(n + 2);

    backtrack(1);

    for (i = 1; i <= n + 1; ++i)
    {
        st[i] = 0;
    }
    for (i = 0; i<y.size(); ++i)
    {
        if (st[y[i].nap] == 0 && st[y[i].nap + 1] == 0)
        {
            st[y[i].nap] = 1;
            st[y[i].nap + 1] = 1;
        }
        else
        {
            do
            {
                if (i < y.size() - 1) y[i] = y[i + 1];
                else
                {
                    y.pop_back();
                    break;
                }
            } while (st[y[i].nap] == 0 && st[y[i].nap + 1] == 0);
        }
    }
    
    int ossz2 = 0;
    for (auto& e : y)
    {
        ossz2 += e.penz;
    }

    if (ossz > ossz2)
    {
        cout << ossz << " " << sol.size() << endl;
        for (auto& e : sol) cout << e << " ";
    }
    else
    {
        cout << ossz2 << " " << y.size() << endl;
        for (auto& e : y) 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és677ms568 KiB
subtask210/10
3Elfogadva1ms316 KiB
4Elfogadva1ms504 KiB
5Elfogadva1ms508 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask30/10
8Időlimit túllépés699ms316 KiB
9Futási hiba1ms316 KiB
10Hibás válasz1ms316 KiB
11Hibás válasz1ms316 KiB
12Hibás válasz1ms316 KiB
subtask40/10
13Elfogadva1ms316 KiB
14Elfogadva1ms504 KiB
15Elfogadva1ms508 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Időlimit túllépés681ms512 KiB
19Hibás válasz1ms500 KiB
20Hibás válasz1ms316 KiB
21Elfogadva1ms508 KiB
22Időlimit túllépés699ms316 KiB
subtask50/10
23Időlimit túllépés699ms316 KiB
24Futási hiba1ms316 KiB
25Hibás válasz1ms316 KiB
26Hibás válasz1ms316 KiB
27Hibás válasz1ms316 KiB
28Hibás válasz2ms500 KiB
29Hibás válasz2ms316 KiB
30Hibás válasz2ms316 KiB
31Hibás válasz2ms508 KiB
32Hibás válasz1ms316 KiB
subtask60/10
33Elfogadva1ms316 KiB
34Elfogadva1ms504 KiB
35Elfogadva1ms508 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Időlimit túllépés699ms316 KiB
39Futási hiba1ms316 KiB
40Hibás válasz1ms316 KiB
41Hibás válasz1ms316 KiB
42Hibás válasz1ms316 KiB
43Időlimit túllépés681ms512 KiB
44Hibás válasz1ms500 KiB
45Hibás válasz1ms316 KiB
46Elfogadva1ms508 KiB
47Időlimit túllépés699ms316 KiB
48Hibás válasz2ms500 KiB
49Hibás válasz2ms316 KiB
50Hibás válasz2ms316 KiB
51Hibás válasz2ms508 KiB
52Hibás válasz1ms316 KiB
53Hibás válasz2ms332 KiB
54Hibás válasz2ms316 KiB
55Hibás válasz1ms316 KiB
56Hibás válasz1ms580 KiB
57Hibás válasz1ms316 KiB
subtask70/10
58Elfogadva1ms316 KiB
59Elfogadva1ms504 KiB
60Elfogadva1ms508 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms316 KiB
63Időlimit túllépés699ms316 KiB
64Futási hiba1ms316 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms316 KiB
67Hibás válasz1ms316 KiB
68Időlimit túllépés681ms512 KiB
69Hibás válasz1ms500 KiB
70Hibás válasz1ms316 KiB
71Elfogadva1ms508 KiB
72Időlimit túllépés699ms316 KiB
73Hibás válasz2ms500 KiB
74Hibás válasz2ms316 KiB
75Hibás válasz2ms316 KiB
76Hibás válasz2ms508 KiB
77Hibás válasz1ms316 KiB
78Hibás válasz2ms332 KiB
79Hibás válasz2ms316 KiB
80Hibás válasz1ms316 KiB
81Hibás válasz1ms580 KiB
82Hibás válasz1ms316 KiB
83Időlimit túllépés699ms1520 KiB
84Időlimit túllépés699ms1520 KiB
85Időlimit túllépés699ms1536 KiB
86Futási hiba37ms1260 KiB
87Futási hiba37ms1332 KiB
subtask80/20
88Elfogadva1ms316 KiB
89Elfogadva1ms504 KiB
90Elfogadva1ms508 KiB
91Elfogadva1ms316 KiB
92Elfogadva1ms316 KiB
93Időlimit túllépés699ms316 KiB
94Futási hiba1ms316 KiB
95Hibás válasz1ms316 KiB
96Hibás válasz1ms316 KiB
97Hibás válasz1ms316 KiB
98Időlimit túllépés681ms512 KiB
99Hibás válasz1ms500 KiB
100Hibás válasz1ms316 KiB
101Elfogadva1ms508 KiB
102Időlimit túllépés699ms316 KiB
103Hibás válasz2ms500 KiB
104Hibás válasz2ms316 KiB
105Hibás válasz2ms316 KiB
106Hibás válasz2ms508 KiB
107Hibás válasz1ms316 KiB
108Hibás válasz2ms332 KiB
109Hibás válasz2ms316 KiB
110Hibás válasz1ms316 KiB
111Hibás válasz1ms580 KiB
112Hibás válasz1ms316 KiB
113Időlimit túllépés699ms1520 KiB
114Időlimit túllépés699ms1520 KiB
115Időlimit túllépés699ms1536 KiB
116Futási hiba37ms1260 KiB
117Futási hiba37ms1332 KiB
118Időlimit túllépés677ms2636 KiB
119Időlimit túllépés677ms2640 KiB
120Időlimit túllépés677ms2636 KiB
121Időlimit túllépés677ms2636 KiB
122Időlimit túllépés680ms2636 KiB
123Időlimit túllépés680ms2648 KiB
124Időlimit túllépés680ms2632 KiB
125Időlimit túllépés680ms2648 KiB
126Időlimit túllépés683ms2684 KiB
127Időlimit túllépés681ms2624 KiB