fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #ifdef LOCAL
  6. #include "algo/debug.h"
  7. #else
  8. #define debug(...) 42
  9. #endif
  10.  
  11. template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y) return x = y, true; return false;}
  12. template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y) return x = y, true; return false;}
  13.  
  14. #define ll long long
  15. #define fi first
  16. #define se second
  17. #define pb push_back
  18. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  19. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  20. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  21. #define C make_pair
  22. #define MASK(i) (1LL << (i))
  23. #define TURN_ON(i, x) ((x) | MASK(i))
  24. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  25. #define CNT(x) (__builtin_popcountll(x))
  26. #define get_bit(i, x) ((x) & MASK(i))
  27. #define REV(i, x) ((x) ^ MASK(i))
  28.  
  29. const ll mod = 1e9 + 7;
  30. const ll INF = 1e15;
  31. const int maxn = 1e5 + 5;
  32. typedef pair<int, int> pi;
  33. typedef pair<int, pair<int,int>> pii;
  34. typedef pair<ll, ll> pl;
  35. typedef pair<ll, pair<ll,ll>>pll;
  36.  
  37. const int MAXN = (int)2e5 + 5;
  38.  
  39. int n, a[MAXN];
  40. ll dp[MAXN][2];
  41. vector<int>ans;
  42.  
  43. void nhap(){
  44.     cin >> n;
  45.     FOR(i, 1, n) cin >> a[i];
  46. }
  47. void solve(){
  48.     FORD(i, n, 1){
  49.         dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]);
  50.         dp[i][1] = dp[i + 1][0] + a[i];
  51.     }
  52.     if(dp[1][1] >= dp[1][0]){
  53.         int i = 1, state = 1;
  54.         ll sum = dp[1][1];
  55.         while(i <= n){
  56.             if(state){
  57.                 ans.pb(i);
  58.                 state = 0;
  59.                 sum -= a[i];
  60.             }
  61.             else{
  62.                 if(dp[i + 1][1] > dp[i + 1][0]) state = 1;
  63.                 else if(dp[i + 1][1] == dp[i + 1][0]){
  64.                     if(sum) state = 1;
  65.                 }
  66.             }
  67.             i++;
  68.         }
  69.     }
  70.     else{
  71.         int i = 1, state = 0;
  72.         ll sum = dp[i][0];
  73.         while(i <= n){
  74.             if(state){
  75.                 ans.pb(i);
  76.                 state = 0;
  77.                 sum -= a[i];
  78.             }
  79.             else{
  80.                 if(dp[i + 1][1] > dp[i + 1][0]) state = 1;
  81.                 else if(dp[i + 1][1] == dp[i + 1][0]){
  82.                     if(sum) state = 1;
  83.                 }
  84.             }
  85.             i++;
  86.         }
  87.     }
  88.     cout << max(dp[1][1], dp[1][0]) << '\n';
  89.     cout << ans.size() << '\n';
  90.     for(int v: ans) cout << v << " ";
  91. }
  92. int main(){
  93.     ios_base::sync_with_stdio(0);
  94.     cin.tie(0); cout.tie(0);
  95.     nhap();
  96.     solve();
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/jKoPIC
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!