Untitled
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