Untitled

 avatar
unknown
plain_text
a year ago
812 B
5
Indexable
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5;
#define ll long long
const int MOD = 1e9+7;
int n,a[N],dp[N],v[N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	freopen("inp.inp","r",stdin);
	// freopen("inp.out","w",stdout);
	cin>>n;
	for (int i = 1;i<=n;i++) cin>>a[i];
	dp[1] = a[1];
	dp[2] = a[1] + a[2];
	for (int i = 3;i<=n;i++)
		dp[i] = max(dp[i-1],max(dp[i-2]+a[i],dp[i-3]+a[i]+a[i-1]));
	int i = n;
	int cnt = 0;
	while (i>0){
		if (dp[i] == dp[i-1]){
			--i;
		}
		if (dp[i] == dp[i-2]+a[i]){
			v[i] = 1;
			i -=2;
			++cnt;
		}
		if (dp[i]==dp[i-3]+a[i]+a[i-1]){
			v[i]=v[i-1] = 1;
			i -=3;cnt+=2;
		}
	}
	cout<<cnt<<' '<<dp[n]<<'\n';
	for (int i = 0;i<=10002;i++) if (v[i] == 1) cout<<i<<'\n';
	return 0;
}
Editor is loading...
Leave a Comment