154872025-02-19 21:51:14999Tűzijátékcpp17Hibás válasz 6/5048ms2356 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,in,k;cin>>n>>in>>k;
    vector<int> v(n);
    for(int i = 0;i<n;i++)cin>>v[i];
    vector<int> dp(n),vissza(n),kovi1(n,-1),kovi2(n,-1);
    int x=0;
    for(int i = 0;i<n;i++){
        x=max(x,i);
        while(x<n&&v[x]-v[i]<k)x++;
        kovi1[i]=x;
    }
    x=n-1;
    for(int i = n-1;i>=0;i--){
        x=min(x,i);
        while(x>=0&&v[i]-v[x]<k)x--;
        kovi2[i]=x;
    }
    in--;
    int i = in-1;
    while(i>=0){
        if(kovi1[i]==-1||kovi1[i]>in){
            dp[i]=1;
            vissza[i]=in;
        }
        else{
            if(1+dp[kovi1[i]]>dp[i+1]){
                dp[i]=1+dp[kovi1[i]];
                vissza[i]=i;
            }
            else{
                dp[i]=dp[i+1];
                vissza[i]=vissza[i+1];
            }
        }
        i--;
    }
    i=in+1;
    while(i<n){
        if(kovi2[i]<in){
            dp[i]=1;
            vissza[i]=in;
        }
        else{
            if(1+dp[kovi2[i]]>dp[i-1]){
                dp[i]=1+dp[kovi2[i]];
                vissza[i]=i;
            }
            else{
                dp[i]=dp[i-1];
                vissza[i]=vissza[i-1];
            }
        }i++;
    }
    cout<<dp[0]+dp[n-1]<<endl;
    i=0;
    deque<int> ans;
    while(i<in){
        cout<<vissza[i]+1<<' ';
        i=vissza[i];
        i++;
    }
    i=n-1;
    while(i>in){
        ans.push_front(vissza[i]+1);
        i=vissza[i];
        i--;
    }
    for(int j : ans)cout<<j<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base6/50
1Elfogadva0/01ms316 KiB
2Hibás válasz0/046ms2356 KiB
3Hibás válasz0/21ms508 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/21ms316 KiB
8Részben helyes1/21ms316 KiB
9Részben helyes1/23ms316 KiB
10Részben helyes1/24ms440 KiB
11Hibás válasz0/24ms564 KiB
12Részben helyes1/28ms732 KiB
13Hibás válasz0/28ms724 KiB
14Hibás válasz0/28ms564 KiB
15Részben helyes1/38ms564 KiB
16Hibás válasz0/313ms768 KiB
17Hibás válasz0/317ms1084 KiB
18Részben helyes1/321ms1332 KiB
19Hibás válasz0/348ms2344 KiB
20Hibás válasz0/346ms2356 KiB
21Hibás válasz0/446ms2340 KiB
22Hibás válasz0/446ms2340 KiB