186162025-10-29 11:02:53KristófMunkákcpp17Részben helyes 44/80689ms2108 KiB
#include <iostream>
#include <vector>

using namespace std;

struct dph
{
int take;
int bestp;
vector<int> taker;
vector<int> bestpr;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> data(n+1,{0,0});
    int x,y;
    for(int i=1;i<=m;i++)
        {
        cin>>x>>y;
        if(y>data[x].first)
            {
            data[x].first=y;
            data[x].second=i;
            }
        }
    dph curr,prev;
    curr.take=data[1].first;
    curr.taker.push_back(data[1].second);
    curr.bestp=0;
    for(int i=2;i<=n;i++)
        {
        prev=curr;
        curr.take=prev.bestp+data[i].first;
        curr.taker=prev.bestpr;
        if(data[i].second!=0)
            curr.taker.push_back(data[i].second);

        if(prev.bestp>prev.take)
            {
            curr.bestp=prev.bestp;
            curr.bestpr=prev.bestpr;
            }
        else
            {
            curr.bestp=prev.take;
            curr.bestpr=prev.taker;
            }
        }
    if(curr.bestp>curr.take)
        {
        cout<<curr.bestp<<" ";

        cout<<curr.bestpr.size()<<endl;
        for(auto x : curr.bestpr)
            {

                cout<<x<<" ";

            }
        }
    else
        {
        cout<<curr.take<<" ";

        cout<<curr.taker.size()<<endl;
        for(auto x : curr.taker)
            {


                cout<<x<<" ";
                }

        }

    //for(auto x : curr.taker)
       // {
       // cout<<x<<" ";
       // }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva35ms564 KiB
subtask210/10
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms508 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask36/10
8Elfogadva1ms316 KiB
9Részben helyes1ms316 KiB
10Elfogadva1ms316 KiB
11Részben helyes1ms508 KiB
12Részben helyes1ms316 KiB
subtask410/10
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms508 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
22Elfogadva1ms320 KiB
subtask56/10
23Elfogadva1ms316 KiB
24Részben helyes1ms316 KiB
25Elfogadva1ms316 KiB
26Részben helyes1ms508 KiB
27Részben helyes1ms316 KiB
28Elfogadva1ms316 KiB
29Elfogadva1ms508 KiB
30Részben helyes1ms500 KiB
31Elfogadva1ms512 KiB
32Részben helyes1ms500 KiB
subtask66/10
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms508 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms316 KiB
39Részben helyes1ms316 KiB
40Elfogadva1ms316 KiB
41Részben helyes1ms508 KiB
42Részben helyes1ms316 KiB
43Elfogadva1ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva1ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva1ms320 KiB
48Elfogadva1ms316 KiB
49Elfogadva1ms508 KiB
50Részben helyes1ms500 KiB
51Elfogadva1ms512 KiB
52Részben helyes1ms500 KiB
53Részben helyes1ms316 KiB
54Részben helyes2ms316 KiB
55Részben helyes2ms508 KiB
56Elfogadva1ms316 KiB
57Részben helyes2ms316 KiB
subtask76/10
58Elfogadva1ms316 KiB
59Elfogadva1ms316 KiB
60Elfogadva1ms508 KiB
61Elfogadva1ms316 KiB
62Elfogadva1ms316 KiB
63Elfogadva1ms316 KiB
64Részben helyes1ms316 KiB
65Elfogadva1ms316 KiB
66Részben helyes1ms508 KiB
67Részben helyes1ms316 KiB
68Elfogadva1ms316 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms320 KiB
73Elfogadva1ms316 KiB
74Elfogadva1ms508 KiB
75Részben helyes1ms500 KiB
76Elfogadva1ms512 KiB
77Részben helyes1ms500 KiB
78Részben helyes1ms316 KiB
79Részben helyes2ms316 KiB
80Részben helyes2ms508 KiB
81Elfogadva1ms316 KiB
82Részben helyes2ms316 KiB
83Elfogadva338ms1616 KiB
84Részben helyes337ms1616 KiB
85Elfogadva337ms1624 KiB
86Elfogadva340ms1596 KiB
87Elfogadva335ms1628 KiB
subtask80/20
88Elfogadva1ms316 KiB
89Elfogadva1ms316 KiB
90Elfogadva1ms508 KiB
91Elfogadva1ms316 KiB
92Elfogadva1ms316 KiB
93Elfogadva1ms316 KiB
94Részben helyes1ms316 KiB
95Elfogadva1ms316 KiB
96Részben helyes1ms508 KiB
97Részben helyes1ms316 KiB
98Elfogadva1ms316 KiB
99Elfogadva1ms316 KiB
100Elfogadva1ms316 KiB
101Elfogadva1ms316 KiB
102Elfogadva1ms320 KiB
103Elfogadva1ms316 KiB
104Elfogadva1ms508 KiB
105Részben helyes1ms500 KiB
106Elfogadva1ms512 KiB
107Részben helyes1ms500 KiB
108Részben helyes1ms316 KiB
109Részben helyes2ms316 KiB
110Részben helyes2ms508 KiB
111Elfogadva1ms316 KiB
112Részben helyes2ms316 KiB
113Elfogadva338ms1616 KiB
114Részben helyes337ms1616 KiB
115Elfogadva337ms1624 KiB
116Elfogadva340ms1596 KiB
117Elfogadva335ms1628 KiB
118Időlimit túllépés666ms2084 KiB
119Időlimit túllépés666ms2096 KiB
120Időlimit túllépés666ms2076 KiB
121Időlimit túllépés667ms2076 KiB
122Időlimit túllépés685ms2088 KiB
123Időlimit túllépés685ms2092 KiB
124Időlimit túllépés685ms2108 KiB
125Időlimit túllépés685ms2096 KiB
126Időlimit túllépés689ms2088 KiB
127Időlimit túllépés689ms2108 KiB