200442025-12-31 11:09:14PappMatyasMunkákcpp17Futási hiba 6/80136ms65536 KiB
#include <iostream>
#include <vector>

using namespace std;

vector<int> dayVal;
vector<int> dayIndex;
vector<int> dp;
vector<vector<int>> sols;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        dayVal.push_back(0);
        dayIndex.push_back(-1);
        sols.push_back(vector<int>(0));
        dp.push_back(0);
    }
    for (int i = 0; i < m; i++)
    {
        int day, val;
        cin >> day >> val;
        day--;
        if (dayVal[day] < val)
        {
            dayVal[day] = val;
            dayIndex[day] = i + 1;
        }
    }
    if (dayVal[0] > dayVal[1])
    {
        dp[0] = dayVal[0];
        dp[1] = dayVal[0];
        if (dayIndex[0] != -1)
        {
            sols[0].reserve(1);
            sols[0] = { dayIndex[0] };
        }
        if (dayIndex[0] != -1)
        {
            sols[1].reserve(1);
            sols[1] = { dayIndex[0] };
        }
    }
    else
    {
        dp[0] = dayVal[1];
        dp[1] = dayVal[1];
        if (dayIndex[1] != -1)
        {
            sols[0].reserve(1);
            sols[0] = { dayIndex[1] };
        }
        if (dayIndex[1] != -1)
        {
            sols[1].reserve(1);
            sols[1] = { dayIndex[1] };
        }
    }
    
    for (int i = 2; i < n; i++)
    {
        if (dp[i - 2] + dayVal[i] > dp[i - 1])
        {
            sols[i].reserve(sols[i - 2].size());
            sols[i].insert(sols[i].end(), sols[i - 2].begin(), sols[i - 2].end());
            if (dayIndex[i] != -1)
            {
                sols[i].push_back(dayIndex[i]);
            }
            dp[i] = dp[i - 2] + dayVal[i];
        }
        else
        {
            sols[i].reserve(sols[i - 1].size());
            sols[i].insert(sols[i].end(), sols[i - 1].begin(), sols[i - 1].end());
            dp[i] = dp[i - 1];
        }
    }
    cout << dp[n - 1] << " " << sols[n - 1].size() << endl;
    for (int ind : sols[n - 1])
    {
        cout << ind << " ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Futási hiba114ms65536 KiB
subtask26/10
3Részben helyes1ms500 KiB
4Elfogadva1ms316 KiB
5Részben helyes1ms316 KiB
6Részben helyes1ms544 KiB
7Részben helyes1ms316 KiB
subtask30/10
8Hibás válasz1ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva1ms316 KiB
subtask40/10
13Részben helyes1ms500 KiB
14Elfogadva1ms316 KiB
15Részben helyes1ms316 KiB
16Részben helyes1ms544 KiB
17Részben helyes1ms316 KiB
18Hibás válasz1ms316 KiB
19Elfogadva1ms316 KiB
20Hibás válasz1ms316 KiB
21Elfogadva1ms316 KiB
22Elfogadva1ms316 KiB
subtask50/10
23Hibás válasz1ms316 KiB
24Elfogadva1ms316 KiB
25Elfogadva1ms316 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva2ms760 KiB
29Elfogadva2ms820 KiB
30Elfogadva2ms824 KiB
31Elfogadva2ms820 KiB
32Elfogadva3ms1136 KiB
subtask60/10
33Részben helyes1ms500 KiB
34Elfogadva1ms316 KiB
35Részben helyes1ms316 KiB
36Részben helyes1ms544 KiB
37Részben helyes1ms316 KiB
38Hibás válasz1ms316 KiB
39Elfogadva1ms316 KiB
40Elfogadva1ms316 KiB
41Elfogadva1ms316 KiB
42Elfogadva1ms316 KiB
43Hibás válasz1ms316 KiB
44Elfogadva1ms316 KiB
45Hibás válasz1ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva1ms316 KiB
48Elfogadva2ms760 KiB
49Elfogadva2ms820 KiB
50Elfogadva2ms824 KiB
51Elfogadva2ms820 KiB
52Elfogadva3ms1136 KiB
53Elfogadva4ms3184 KiB
54Elfogadva4ms2928 KiB
55Elfogadva4ms2928 KiB
56Elfogadva4ms2672 KiB
57Elfogadva4ms2928 KiB
subtask70/10
58Részben helyes1ms500 KiB
59Elfogadva1ms316 KiB
60Részben helyes1ms316 KiB
61Részben helyes1ms544 KiB
62Részben helyes1ms316 KiB
63Hibás válasz1ms316 KiB
64Elfogadva1ms316 KiB
65Elfogadva1ms316 KiB
66Elfogadva1ms316 KiB
67Elfogadva1ms316 KiB
68Hibás válasz1ms316 KiB
69Elfogadva1ms316 KiB
70Hibás válasz1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva2ms760 KiB
74Elfogadva2ms820 KiB
75Elfogadva2ms824 KiB
76Elfogadva2ms820 KiB
77Elfogadva3ms1136 KiB
78Elfogadva4ms3184 KiB
79Elfogadva4ms2928 KiB
80Elfogadva4ms2928 KiB
81Elfogadva4ms2672 KiB
82Elfogadva4ms2928 KiB
83Futási hiba98ms65536 KiB
84Futási hiba100ms65536 KiB
85Futási hiba89ms65536 KiB
86Futási hiba89ms65536 KiB
87Futási hiba97ms65536 KiB
subtask80/20
88Részben helyes1ms500 KiB
89Elfogadva1ms316 KiB
90Részben helyes1ms316 KiB
91Részben helyes1ms544 KiB
92Részben helyes1ms316 KiB
93Hibás válasz1ms316 KiB
94Elfogadva1ms316 KiB
95Elfogadva1ms316 KiB
96Elfogadva1ms316 KiB
97Elfogadva1ms316 KiB
98Hibás válasz1ms316 KiB
99Elfogadva1ms316 KiB
100Hibás válasz1ms316 KiB
101Elfogadva1ms316 KiB
102Elfogadva1ms316 KiB
103Elfogadva2ms760 KiB
104Elfogadva2ms820 KiB
105Elfogadva2ms824 KiB
106Elfogadva2ms820 KiB
107Elfogadva3ms1136 KiB
108Elfogadva4ms3184 KiB
109Elfogadva4ms2928 KiB
110Elfogadva4ms2928 KiB
111Elfogadva4ms2672 KiB
112Elfogadva4ms2928 KiB
113Futási hiba98ms65536 KiB
114Futási hiba100ms65536 KiB
115Futási hiba89ms65536 KiB
116Futási hiba89ms65536 KiB
117Futási hiba97ms65536 KiB
118Futási hiba134ms65536 KiB
119Futási hiba135ms65536 KiB
120Futási hiba120ms65536 KiB
121Futási hiba123ms65536 KiB
122Futási hiba133ms65536 KiB
123Futási hiba133ms65536 KiB
124Futási hiba123ms65536 KiB
125Futási hiba133ms65536 KiB
126Futási hiba136ms65536 KiB
127Futási hiba134ms65536 KiB