230762026-01-16 11:41:17gyarturMunkákcpp17Partially correct 12/8071ms2996 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Munka{
    int nap;
    int bevetel;
    int index;
};

int n, m;
int utolso;
int utolsoNap = 0;
vector<Munka> legnagyobbMunka;
vector<long long> maxBevetel;
vector<int> elozoNap;

void Beolvas(){
    cin>>n>>m;
    maxBevetel.resize(n+1, 0);
    elozoNap.resize(n+1, 0);
    legnagyobbMunka.resize(n+1, {0,0,0});
    Munka munka;
    for(int i = 1; i <= m; i++){
        cin>>munka.nap>>munka.bevetel;
        utolsoNap = max(utolsoNap, munka.nap);
        if(legnagyobbMunka[munka.nap].bevetel < munka.bevetel){
            munka.index = i;
            legnagyobbMunka[munka.nap] = munka;
        }
    }
}

void Feladat(){
    maxBevetel[1] = legnagyobbMunka[1].bevetel;
    maxBevetel[2] = legnagyobbMunka[2].bevetel;
    maxBevetel[3] = maxBevetel[1] + legnagyobbMunka[3].bevetel;
    for(int i = 4; i <= utolsoNap; i++){
        if(legnagyobbMunka[i].index){
            maxBevetel[i] = legnagyobbMunka[i].bevetel;
            for(int j = i-4; j < i-1; j++){
                if(maxBevetel[j] + legnagyobbMunka[i].bevetel > maxBevetel[i]){
                    maxBevetel[i] = maxBevetel[j] + legnagyobbMunka[i].bevetel;
                    elozoNap[i] = j;
                }
            }
            if(maxBevetel[i] > maxBevetel[utolso])utolso = i;
        }
    }
}

void Kiir(){
    vector<int> kiirat;
    kiirat.reserve(n+1);
    int i = utolso;
    do{
        kiirat.push_back(legnagyobbMunka[i].index);
    }while(i = elozoNap[i]);
    cout<<maxBevetel[utolso]<<' '<<kiirat.size()<<'\n';
    for(int x : kiirat){
        cout<<x<<' ';
    }
}
        
int main(){
    Beolvas();
    Feladat();
    Kiir();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Partially correct59ms756 KiB
subtask26/10
3Partially correct1ms512 KiB
4Accepted2ms316 KiB
5Partially correct1ms316 KiB
6Partially correct2ms508 KiB
7Partially correct1ms316 KiB
subtask30/10
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Wrong answer1ms316 KiB
11Wrong answer1ms316 KiB
12Wrong answer1ms316 KiB
subtask46/10
13Partially correct1ms512 KiB
14Accepted2ms316 KiB
15Partially correct1ms316 KiB
16Partially correct2ms508 KiB
17Partially correct1ms316 KiB
18Accepted1ms316 KiB
19Partially correct1ms316 KiB
20Partially correct1ms500 KiB
21Partially correct1ms316 KiB
22Partially correct1ms316 KiB
subtask50/10
23Wrong answer1ms316 KiB
24Wrong answer1ms316 KiB
25Wrong answer1ms316 KiB
26Wrong answer1ms316 KiB
27Wrong answer1ms316 KiB
28Wrong answer1ms316 KiB
29Wrong answer1ms316 KiB
30Wrong answer1ms564 KiB
31Wrong answer1ms564 KiB
32Wrong answer1ms564 KiB
subtask60/10
33Partially correct1ms512 KiB
34Accepted2ms316 KiB
35Partially correct1ms316 KiB
36Partially correct2ms508 KiB
37Partially correct1ms316 KiB
38Wrong answer1ms316 KiB
39Wrong answer1ms316 KiB
40Wrong answer1ms316 KiB
41Wrong answer1ms316 KiB
42Wrong answer1ms316 KiB
43Accepted1ms316 KiB
44Partially correct1ms316 KiB
45Partially correct1ms500 KiB
46Partially correct1ms316 KiB
47Partially correct1ms316 KiB
48Wrong answer1ms316 KiB
49Wrong answer1ms316 KiB
50Wrong answer1ms564 KiB
51Wrong answer1ms564 KiB
52Wrong answer1ms564 KiB
53Wrong answer1ms748 KiB
54Wrong answer1ms564 KiB
55Wrong answer1ms564 KiB
56Wrong answer1ms564 KiB
57Wrong answer1ms564 KiB
subtask70/10
58Partially correct1ms512 KiB
59Accepted2ms316 KiB
60Partially correct1ms316 KiB
61Partially correct2ms508 KiB
62Partially correct1ms316 KiB
63Wrong answer1ms316 KiB
64Wrong answer1ms316 KiB
65Wrong answer1ms316 KiB
66Wrong answer1ms316 KiB
67Wrong answer1ms316 KiB
68Accepted1ms316 KiB
69Partially correct1ms316 KiB
70Partially correct1ms500 KiB
71Partially correct1ms316 KiB
72Partially correct1ms316 KiB
73Wrong answer1ms316 KiB
74Wrong answer1ms316 KiB
75Wrong answer1ms564 KiB
76Wrong answer1ms564 KiB
77Wrong answer1ms564 KiB
78Wrong answer1ms748 KiB
79Wrong answer1ms564 KiB
80Wrong answer1ms564 KiB
81Wrong answer1ms564 KiB
82Wrong answer1ms564 KiB
83Wrong answer32ms1580 KiB
84Wrong answer35ms1584 KiB
85Wrong answer34ms1588 KiB
86Wrong answer35ms1580 KiB
87Wrong answer34ms1588 KiB
subtask80/20
88Partially correct1ms512 KiB
89Accepted2ms316 KiB
90Partially correct1ms316 KiB
91Partially correct2ms508 KiB
92Partially correct1ms316 KiB
93Wrong answer1ms316 KiB
94Wrong answer1ms316 KiB
95Wrong answer1ms316 KiB
96Wrong answer1ms316 KiB
97Wrong answer1ms316 KiB
98Accepted1ms316 KiB
99Partially correct1ms316 KiB
100Partially correct1ms500 KiB
101Partially correct1ms316 KiB
102Partially correct1ms316 KiB
103Wrong answer1ms316 KiB
104Wrong answer1ms316 KiB
105Wrong answer1ms564 KiB
106Wrong answer1ms564 KiB
107Wrong answer1ms564 KiB
108Wrong answer1ms748 KiB
109Wrong answer1ms564 KiB
110Wrong answer1ms564 KiB
111Wrong answer1ms564 KiB
112Wrong answer1ms564 KiB
113Wrong answer32ms1580 KiB
114Wrong answer35ms1584 KiB
115Wrong answer34ms1588 KiB
116Wrong answer35ms1580 KiB
117Wrong answer34ms1588 KiB
118Wrong answer68ms2796 KiB
119Wrong answer70ms2612 KiB
120Wrong answer68ms2704 KiB
121Wrong answer68ms2804 KiB
122Wrong answer68ms2808 KiB
123Wrong answer67ms2804 KiB
124Wrong answer68ms2764 KiB
125Wrong answer68ms2612 KiB
126Wrong answer68ms2612 KiB
127Wrong answer71ms2996 KiB