Untitled

 avatar
user_0483151
plain_text
6 months ago
1.4 kB
3
Indexable
// muzik
#include <bits/stdc++.h>
#define cook '\n'
#define maxn
#define Task "bai1"
using namespace std;
int n;
vector<int> v,dp,tr,step ;

int Find(int pos) {
    if ( dp[pos] == dp[pos-3]+v[pos]+v[pos-1] ) return 1 ;
    if ( dp[pos] == dp[pos-2]+v[pos] ) return 2;
    return 3 ;
}

int solve(int pos) {
    if ( tr[pos] == 1 ) {
        step.push_back(pos) ;
        step.push_back(pos-1) ;
        return pos-3 ;
    }
    if ( tr[pos] == 2 ) {
        step.push_back(pos) ;
        return pos-2;
    }
    return pos-1;
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if(fopen(Task".INP","r")) {
        freopen(Task".INP","r",stdin);
        freopen(Task".OUT","w",stdout);
    }
    cin >> n;
    v.resize(n+1) ;
    dp.resize(n+1) ;
    tr.resize(n+1) ;
    for ( int i = 1; i <= n; i++ ) cin >> v[i] ;
    dp[1] = max(v[1],0);
    if (dp[1]==v[1]) tr[1]=2;
    dp[2] = max({dp[1]+v[2],0,dp[1]});
    if (dp[2]==dp[1]+v[2]) tr[2]=1;
        else if (dp[2]==dp[1]) tr[2]=3;
    for ( int i = 3; i <= n; i++ ) {
        dp[i] = max({dp[i-3]+v[i]+v[i-1],dp[i-2]+v[i],dp[i-1]}) ;
        tr[i] = Find(i);
    }
    cout << dp[n] << cook ;
    int pos = n;
    while ( pos > 0 )
        pos = solve(pos) ;
    for ( int i = step.size(); i ; i-- ) cout << step[i-1] << " " ;
}
Editor is loading...
Leave a Comment