197502025-12-21 14:09:41szabel26Munkákcpp17Time limit exceeded 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
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded677ms568 KiB
subtask210/10
3Accepted1ms316 KiB
4Accepted1ms504 KiB
5Accepted1ms508 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask30/10
8Time limit exceeded699ms316 KiB
9Runtime error1ms316 KiB
10Wrong answer1ms316 KiB
11Wrong answer1ms316 KiB
12Wrong answer1ms316 KiB
subtask40/10
13Accepted1ms316 KiB
14Accepted1ms504 KiB
15Accepted1ms508 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Time limit exceeded681ms512 KiB
19Wrong answer1ms500 KiB
20Wrong answer1ms316 KiB
21Accepted1ms508 KiB
22Time limit exceeded699ms316 KiB
subtask50/10
23Time limit exceeded699ms316 KiB
24Runtime error1ms316 KiB
25Wrong answer1ms316 KiB
26Wrong answer1ms316 KiB
27Wrong answer1ms316 KiB
28Wrong answer2ms500 KiB
29Wrong answer2ms316 KiB
30Wrong answer2ms316 KiB
31Wrong answer2ms508 KiB
32Wrong answer1ms316 KiB
subtask60/10
33Accepted1ms316 KiB
34Accepted1ms504 KiB
35Accepted1ms508 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Time limit exceeded699ms316 KiB
39Runtime error1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms316 KiB
43Time limit exceeded681ms512 KiB
44Wrong answer1ms500 KiB
45Wrong answer1ms316 KiB
46Accepted1ms508 KiB
47Time limit exceeded699ms316 KiB
48Wrong answer2ms500 KiB
49Wrong answer2ms316 KiB
50Wrong answer2ms316 KiB
51Wrong answer2ms508 KiB
52Wrong answer1ms316 KiB
53Wrong answer2ms332 KiB
54Wrong answer2ms316 KiB
55Wrong answer1ms316 KiB
56Wrong answer1ms580 KiB
57Wrong answer1ms316 KiB
subtask70/10
58Accepted1ms316 KiB
59Accepted1ms504 KiB
60Accepted1ms508 KiB
61Accepted1ms316 KiB
62Accepted1ms316 KiB
63Time limit exceeded699ms316 KiB
64Runtime error1ms316 KiB
65Wrong answer1ms316 KiB
66Wrong answer1ms316 KiB
67Wrong answer1ms316 KiB
68Time limit exceeded681ms512 KiB
69Wrong answer1ms500 KiB
70Wrong answer1ms316 KiB
71Accepted1ms508 KiB
72Time limit exceeded699ms316 KiB
73Wrong answer2ms500 KiB
74Wrong answer2ms316 KiB
75Wrong answer2ms316 KiB
76Wrong answer2ms508 KiB
77Wrong answer1ms316 KiB
78Wrong answer2ms332 KiB
79Wrong answer2ms316 KiB
80Wrong answer1ms316 KiB
81Wrong answer1ms580 KiB
82Wrong answer1ms316 KiB
83Time limit exceeded699ms1520 KiB
84Time limit exceeded699ms1520 KiB
85Time limit exceeded699ms1536 KiB
86Runtime error37ms1260 KiB
87Runtime error37ms1332 KiB
subtask80/20
88Accepted1ms316 KiB
89Accepted1ms504 KiB
90Accepted1ms508 KiB
91Accepted1ms316 KiB
92Accepted1ms316 KiB
93Time limit exceeded699ms316 KiB
94Runtime error1ms316 KiB
95Wrong answer1ms316 KiB
96Wrong answer1ms316 KiB
97Wrong answer1ms316 KiB
98Time limit exceeded681ms512 KiB
99Wrong answer1ms500 KiB
100Wrong answer1ms316 KiB
101Accepted1ms508 KiB
102Time limit exceeded699ms316 KiB
103Wrong answer2ms500 KiB
104Wrong answer2ms316 KiB
105Wrong answer2ms316 KiB
106Wrong answer2ms508 KiB
107Wrong answer1ms316 KiB
108Wrong answer2ms332 KiB
109Wrong answer2ms316 KiB
110Wrong answer1ms316 KiB
111Wrong answer1ms580 KiB
112Wrong answer1ms316 KiB
113Time limit exceeded699ms1520 KiB
114Time limit exceeded699ms1520 KiB
115Time limit exceeded699ms1536 KiB
116Runtime error37ms1260 KiB
117Runtime error37ms1332 KiB
118Time limit exceeded677ms2636 KiB
119Time limit exceeded677ms2640 KiB
120Time limit exceeded677ms2636 KiB
121Time limit exceeded677ms2636 KiB
122Time limit exceeded680ms2636 KiB
123Time limit exceeded680ms2648 KiB
124Time limit exceeded680ms2632 KiB
125Time limit exceeded680ms2648 KiB
126Time limit exceeded683ms2684 KiB
127Time limit exceeded681ms2624 KiB