• API
• FAQ
• Tools
• Archive
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>
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);
22.     }
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.
Top