294282026-06-09 21:39:20KristófHegymászó **cpp17Elfogadva 100/10016ms8428 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,cel,cap;cin>>n>>cel>>cap;
    vector<pair<int,int>> pontok(n+1);
    for(int i=1;i<=n;i++)
        {
        int x,y;cin>>x>>y;
        pontok[i]={x,y};
        }
    vector<vector<int>> dp(n+10,vector<int> (n+10,0));
    vector<vector<int>> honnan(n+1,vector<int> (n+1,-1));
    //dp[1][1]=min(cap,pontok[1].second);
    //honnan[1][1]=1;
    for(int taken=1;taken<=n;taken++)
        {
        for(int len=1;len<=n;len++)
            {
            // nem allok meg itt
            int tav=pontok[len].first-pontok[len-1].first;
            honnan[taken][len]=0;//nem allok meg
            dp[taken][len]=dp[taken][len-1]-tav;

            if(tav<=dp[taken-1][len-1])
                {
                if(dp[taken-1][len-1]-tav+pontok[len].second>dp[taken][len])honnan[taken][len]=1;
                dp[taken][len]=max(dp[taken][len],dp[taken-1][len-1]-tav+pontok[len].second);

                }

            dp[taken][len]=min(dp[taken][len],cap);
            }
        }
    int lasttav=cel-pontok[n].first;
    int stopcnt=1;
    for(;stopcnt<=n;stopcnt++)if(dp[stopcnt][n]>=lasttav){cout<<stopcnt<<"\n";break;}
    vector<int> ans;
    int i,j;
    i=stopcnt;j=n;
    while(true)
        {
        if(!i || !j)break;
        if(honnan[i][j])
            {
            ans.push_back(j);
            i--;j--;
            }
        else j--;
        }
    reverse(ans.begin(),ans.end());
    for(int x:ans)cout<<x<<" ";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva6/61ms508 KiB
2Elfogadva6/61ms328 KiB
3Elfogadva6/61ms492 KiB
4Elfogadva6/61ms328 KiB
5Elfogadva6/61ms328 KiB
6Elfogadva7/71ms328 KiB
7Elfogadva7/71ms576 KiB
8Elfogadva7/71ms328 KiB
9Elfogadva7/71ms328 KiB
10Elfogadva7/76ms3136 KiB
11Elfogadva7/714ms8256 KiB
12Elfogadva7/716ms8416 KiB
13Elfogadva7/714ms8260 KiB
14Elfogadva7/716ms8428 KiB
15Elfogadva7/714ms8256 KiB