200452025-12-31 11:13:00PappMatyasMunkákcpp17Runtime error 50/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[0];
        dp[1] = dayVal[1];
        if (dayIndex[0] != -1)
        {
            sols[0].reserve(1);
            sols[0] = { dayIndex[0] };
        }
        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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Runtime error123ms65536 KiB
subtask210/10
3Accepted1ms324 KiB
4Accepted2ms500 KiB
5Accepted1ms500 KiB
6Accepted2ms316 KiB
7Accepted1ms316 KiB
subtask310/10
8Accepted1ms316 KiB
9Accepted1ms568 KiB
10Accepted2ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask410/10
13Accepted1ms324 KiB
14Accepted2ms500 KiB
15Accepted1ms500 KiB
16Accepted2ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms508 KiB
subtask510/10
23Accepted1ms316 KiB
24Accepted1ms568 KiB
25Accepted2ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted2ms564 KiB
29Accepted2ms820 KiB
30Accepted2ms820 KiB
31Accepted3ms820 KiB
32Accepted3ms1136 KiB
subtask610/10
33Accepted1ms324 KiB
34Accepted2ms500 KiB
35Accepted1ms500 KiB
36Accepted2ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted1ms568 KiB
40Accepted2ms316 KiB
41Accepted1ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Accepted1ms316 KiB
45Accepted1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms508 KiB
48Accepted2ms564 KiB
49Accepted2ms820 KiB
50Accepted2ms820 KiB
51Accepted3ms820 KiB
52Accepted3ms1136 KiB
53Accepted4ms3184 KiB
54Accepted4ms2928 KiB
55Accepted4ms2928 KiB
56Accepted4ms2928 KiB
57Accepted4ms2780 KiB
subtask70/10
58Accepted1ms324 KiB
59Accepted2ms500 KiB
60Accepted1ms500 KiB
61Accepted2ms316 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms568 KiB
65Accepted2ms316 KiB
66Accepted1ms316 KiB
67Accepted1ms316 KiB
68Accepted1ms316 KiB
69Accepted1ms316 KiB
70Accepted1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms508 KiB
73Accepted2ms564 KiB
74Accepted2ms820 KiB
75Accepted2ms820 KiB
76Accepted3ms820 KiB
77Accepted3ms1136 KiB
78Accepted4ms3184 KiB
79Accepted4ms2928 KiB
80Accepted4ms2928 KiB
81Accepted4ms2928 KiB
82Accepted4ms2780 KiB
83Runtime error87ms65536 KiB
84Runtime error87ms65536 KiB
85Runtime error98ms65536 KiB
86Runtime error98ms65536 KiB
87Runtime error100ms65536 KiB
subtask80/20
88Accepted1ms324 KiB
89Accepted2ms500 KiB
90Accepted1ms500 KiB
91Accepted2ms316 KiB
92Accepted1ms316 KiB
93Accepted1ms316 KiB
94Accepted1ms568 KiB
95Accepted2ms316 KiB
96Accepted1ms316 KiB
97Accepted1ms316 KiB
98Accepted1ms316 KiB
99Accepted1ms316 KiB
100Accepted1ms316 KiB
101Accepted1ms316 KiB
102Accepted1ms508 KiB
103Accepted2ms564 KiB
104Accepted2ms820 KiB
105Accepted2ms820 KiB
106Accepted3ms820 KiB
107Accepted3ms1136 KiB
108Accepted4ms3184 KiB
109Accepted4ms2928 KiB
110Accepted4ms2928 KiB
111Accepted4ms2928 KiB
112Accepted4ms2780 KiB
113Runtime error87ms65536 KiB
114Runtime error87ms65536 KiB
115Runtime error98ms65536 KiB
116Runtime error98ms65536 KiB
117Runtime error100ms65536 KiB
118Runtime error133ms65536 KiB
119Runtime error123ms65536 KiB
120Runtime error123ms65536 KiB
121Runtime error134ms65536 KiB
122Runtime error133ms65536 KiB
123Runtime error119ms65536 KiB
124Runtime error131ms65536 KiB
125Runtime error131ms65536 KiB
126Runtime error136ms65536 KiB
127Runtime error131ms65536 KiB