200442025-12-31 11:09:14PappMatyasMunkákcpp17Runtime error 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Runtime error114ms65536 KiB
subtask26/10
3Partially correct1ms500 KiB
4Accepted1ms316 KiB
5Partially correct1ms316 KiB
6Partially correct1ms544 KiB
7Partially correct1ms316 KiB
subtask30/10
8Wrong answer1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Accepted1ms316 KiB
12Accepted1ms316 KiB
subtask40/10
13Partially correct1ms500 KiB
14Accepted1ms316 KiB
15Partially correct1ms316 KiB
16Partially correct1ms544 KiB
17Partially correct1ms316 KiB
18Wrong answer1ms316 KiB
19Accepted1ms316 KiB
20Wrong answer1ms316 KiB
21Accepted1ms316 KiB
22Accepted1ms316 KiB
subtask50/10
23Wrong answer1ms316 KiB
24Accepted1ms316 KiB
25Accepted1ms316 KiB
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted2ms760 KiB
29Accepted2ms820 KiB
30Accepted2ms824 KiB
31Accepted2ms820 KiB
32Accepted3ms1136 KiB
subtask60/10
33Partially correct1ms500 KiB
34Accepted1ms316 KiB
35Partially correct1ms316 KiB
36Partially correct1ms544 KiB
37Partially correct1ms316 KiB
38Wrong answer1ms316 KiB
39Accepted1ms316 KiB
40Accepted1ms316 KiB
41Accepted1ms316 KiB
42Accepted1ms316 KiB
43Wrong answer1ms316 KiB
44Accepted1ms316 KiB
45Wrong answer1ms316 KiB
46Accepted1ms316 KiB
47Accepted1ms316 KiB
48Accepted2ms760 KiB
49Accepted2ms820 KiB
50Accepted2ms824 KiB
51Accepted2ms820 KiB
52Accepted3ms1136 KiB
53Accepted4ms3184 KiB
54Accepted4ms2928 KiB
55Accepted4ms2928 KiB
56Accepted4ms2672 KiB
57Accepted4ms2928 KiB
subtask70/10
58Partially correct1ms500 KiB
59Accepted1ms316 KiB
60Partially correct1ms316 KiB
61Partially correct1ms544 KiB
62Partially correct1ms316 KiB
63Wrong answer1ms316 KiB
64Accepted1ms316 KiB
65Accepted1ms316 KiB
66Accepted1ms316 KiB
67Accepted1ms316 KiB
68Wrong answer1ms316 KiB
69Accepted1ms316 KiB
70Wrong answer1ms316 KiB
71Accepted1ms316 KiB
72Accepted1ms316 KiB
73Accepted2ms760 KiB
74Accepted2ms820 KiB
75Accepted2ms824 KiB
76Accepted2ms820 KiB
77Accepted3ms1136 KiB
78Accepted4ms3184 KiB
79Accepted4ms2928 KiB
80Accepted4ms2928 KiB
81Accepted4ms2672 KiB
82Accepted4ms2928 KiB
83Runtime error98ms65536 KiB
84Runtime error100ms65536 KiB
85Runtime error89ms65536 KiB
86Runtime error89ms65536 KiB
87Runtime error97ms65536 KiB
subtask80/20
88Partially correct1ms500 KiB
89Accepted1ms316 KiB
90Partially correct1ms316 KiB
91Partially correct1ms544 KiB
92Partially correct1ms316 KiB
93Wrong answer1ms316 KiB
94Accepted1ms316 KiB
95Accepted1ms316 KiB
96Accepted1ms316 KiB
97Accepted1ms316 KiB
98Wrong answer1ms316 KiB
99Accepted1ms316 KiB
100Wrong answer1ms316 KiB
101Accepted1ms316 KiB
102Accepted1ms316 KiB
103Accepted2ms760 KiB
104Accepted2ms820 KiB
105Accepted2ms824 KiB
106Accepted2ms820 KiB
107Accepted3ms1136 KiB
108Accepted4ms3184 KiB
109Accepted4ms2928 KiB
110Accepted4ms2928 KiB
111Accepted4ms2672 KiB
112Accepted4ms2928 KiB
113Runtime error98ms65536 KiB
114Runtime error100ms65536 KiB
115Runtime error89ms65536 KiB
116Runtime error89ms65536 KiB
117Runtime error97ms65536 KiB
118Runtime error134ms65536 KiB
119Runtime error135ms65536 KiB
120Runtime error120ms65536 KiB
121Runtime error123ms65536 KiB
122Runtime error133ms65536 KiB
123Runtime error133ms65536 KiB
124Runtime error123ms65536 KiB
125Runtime error133ms65536 KiB
126Runtime error136ms65536 KiB
127Runtime error134ms65536 KiB