SHARE
TWEET

Untitled

a guest Feb 14th, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <cmath>
  4. #include <queue>
  5. #include <algorithm>
  6. #define task ""
  7. #define pb push_back
  8. #define ld long double
  9. #define ll long long
  10. #define ull unsigned long long
  11.  
  12. using namespace std;
  13. const int sizearr = 100003;
  14.  
  15. inline void fastIOfileinput(){
  16.     ios_base:: sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.     if(fopen(task".inp", "r")){
  20.         freopen(task".inp", "r", stdin);
  21.         freopen(task".out", "w", stdout);
  22.     }
  23.     if(fopen(task".in", "r")){
  24.         freopen(task".in", "r", stdin);
  25.         freopen(task".out", "w", stdout);
  26.     }
  27. }
  28.  
  29. ll n, a[100009], sum;
  30. int m;
  31. ll f[100009];
  32. bool ck[4][100009];
  33. inline void Enter(){
  34.     cin >> n;
  35.     for(int i = 1; i <= n; ++i) cin >> a[i];
  36. }
  37.  
  38. void trace(int i){
  39.     if(i == 1){
  40.         cout << 1 << " ";
  41.         return;
  42.     }
  43.     if(i == 2){
  44.         cout << "1 2 ";
  45.         return;
  46.     }
  47.     if(ck[2][i]){
  48.             trace(i - 2);
  49.         cout << i << " ";
  50.     }
  51.     if(ck[3][i]){
  52.             trace(i - 3);
  53.         cout << i - 1 << " " << i << " ";
  54.     }
  55.     if(ck[1][i]) trace(i - 1);
  56. }
  57.  
  58. inline void solve(){
  59.     f[1] = 1;
  60.     f[2] = f[1] + a[2];
  61.     for(int i = 3; i <= n; ++i){
  62.         ck[1][i] = ck[2][i] = ck[3][i] = 0;
  63.         f[i] = max(f[i - 1], max(f[i - 2] + a[i], f[i - 3] + a[i] + a[i - 1]));
  64.         if(f[i] == f[i - 1]) ck[1][i] = 1;
  65.         else if(f[i] == f[i - 2] + a[i]) ck[2][i] = 1;
  66.         else ck[3][i] = 1;
  67.     }
  68.     cout << f[n] << "\n";
  69.     trace(n);
  70. }
  71.  
  72. int main(){
  73.     fastIOfileinput();
  74.     int t;
  75.     Enter();
  76.     solve();
  77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top