fork download
copy 
  1. /* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */
  2. /* Enjoy TheFatRat's music while reading my code. Link: https://w...content-available-to-author-only...e.com/watch?v=GCx9FU59FJc&t=669s */
  3.  
  4. //#pragma GCC optimize("O3", "unroll-loops")
  5. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  6.  
  7. #include <bits/stdc++.h>
  8. #define ldb long double
  9. //#define double ldb
  10. #define db double
  11. #define name "test"
  12. #define unomap unordered_map
  13. #define unoset unordered_set
  14. #define endl '\n'
  15. #define str string
  16. #define strstr stringstream
  17. #define sz(a) a.size()
  18. #define ll long long
  19. //#define int ll
  20. #define pii pair <int, int>
  21. #define pll pair <ll, ll>
  22. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  23. #define ull unsigned ll
  24. #define fir first
  25. #define sec second
  26. #define idc cin.ignore()
  27. #define lb lower_bound
  28. #define ub upper_bound
  29. #define all(s) s.begin(), s.end()
  30. #define rev reverse
  31. #define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  32. #define skibidi int main
  33. #define rizz signed main
  34. #define gcd __gcd
  35. #define found(a, mp) mp.find(a) != mp.end()
  36. #define game_over exit(0);
  37. #define stfu return 0;
  38. #define stop break;
  39. #define odd(n) n & 1
  40. #define pushb push_back
  41. #define popb pop_back
  42. #define pushf push_front
  43. #define popf pop_front
  44. #define even(n) !odd(n)
  45. #define mul2x(a, x) a << x
  46. #define div2x(a, x) a >> x
  47. #define no_check continue;
  48. #define lcm(a, b) a / __gcd(a, b) * b
  49. #define log_base(x, base) log(x) / log(base)
  50. #define debug clog << "No errors!"; game_over;
  51. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  52. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  53. #define fors(i, a, b) for (int i = a; i >= b; --i)
  54. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  55. #define meme memset
  56. #define pqueue priority_queue
  57. #define want_digit(x) cout << fixed << setprecision(x);
  58. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  59. #define pil pair <int, ll>
  60. using namespace std;
  61. const int MOD = 1e9 + 7; // 998244353
  62. const int inf = 1e9;
  63. const ll INF = 1e18;
  64. const int N = 4e5;
  65.  
  66. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  67. ll random(const ll &L, const ll &R)
  68. {
  69.     return uniform_int_distribution<ll> (L, R) (rng);
  70. }
  71.  
  72. template <class X, class Y>
  73. bool maximize(X &x, const Y &y)
  74. {
  75.     return x < y ? x = y, true : false;
  76. }
  77.  
  78. struct query
  79. {
  80.     int last, start, finish;
  81.     query()
  82.     {
  83.         last = 0;
  84.     }
  85. };
  86.  
  87. pil mx(const pil &x, const pil &y)
  88. {
  89.     if (x.sec >= y.sec)
  90.         return x;
  91.     return y;
  92. }
  93.  
  94. query res[N + 5];
  95. int n, k, a[N + 5];
  96. ll sum[N + 5], dp[N + 5], ans = 0;
  97. pil pre[N + 5];
  98. deque <int> dq;
  99.  
  100. ll get(int ind)
  101. {
  102.     return pre[ind - 2].sec - sum[ind - 1];
  103. }
  104.  
  105. void cook()
  106. {
  107.     cin >> n >> k;
  108.     forw (i, 1, n) cin >> a[i], sum[i] = sum[i - 1] + a[i];
  109.  
  110.     forw (i, 1, k - 1)
  111.     {
  112.         dp[i] = sum[i];
  113.         pre[i] = mx(pre[i - 1], pil(i, dp[i]));
  114.         res[i].last = i - 1; res[i].start = 1; res[i].finish = i;
  115.     }
  116.  
  117.     forw (i, 2, k - 1)
  118.     {
  119.         while (!dq.empty() && get(dq.back()) <= get(i)) dq.popf();
  120.         dq.pushb(i);
  121.     }
  122.  
  123.     forw (i, k, n)
  124.     {
  125.         while (!dq.empty() && dq.front() < i - k + 2) dq.popf();
  126.         while (!dq.empty() && get(dq.back()) <= get(i)) dq.popb();
  127.         dq.pushb(i);
  128.         dp[i] = sum[i] + get(dq.front());
  129.         pre[i] = mx(pre[i - 1], pil(i, dp[i]));
  130.         res[i].last = pre[dq.front() - 2].first;
  131.         res[i].start = dq.front(); res[i].finish = i;
  132.     }
  133.  
  134.     ll ans = 0;
  135.     int ind = 1;
  136.     forw (i, 1, n)
  137.         if (maximize(ans, dp[i])) ind = i;
  138.  
  139.     vector <int> v;
  140.     while (ind)
  141.     {
  142.         fors (i, res[ind].finish, res[ind].start) v.pushb(i);
  143.         ind = res[ind].last;
  144.     }
  145.     rev(all(v));
  146.     cout << sz(v) << ' ' << ans << endl;
  147.     forw (i, 0, sz(v) - 1) cout << v[i] << ' ';
  148.     cout << endl;
  149. }
  150.  
  151. skibidi()
  152. //rizz()
  153. {
  154.     srand(time(NULL));
  155.     sigma;
  156.     /*
  157.     if (fopen(name".INP", "r"))
  158.     {
  159.         freopen(name".INP", "r", stdin);
  160.         freopen(name".OUT", "w", stdout);
  161.     }
  162.     */
  163.     int numTest = 1;
  164. //    cin >> numTest;
  165.     while (numTest--)
  166.     {
  167.         cook();
  168.     }
  169.     stfu;
  170. }
  171.  
Success #stdin #stdout 0.01s 13700KB
comments (?)
stdin
copy 
5 10
5 6 7 8 6
stdout
copy 
15 32
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5
https://ideone.com/K7PmBC
language:
C++14 (gcc 8.3)
created:
7 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!