fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <bits/stdc++.h>
  5.  
  6. #define mp make_pair
  7. #define all(c) (c).begin() , (c).end()
  8. #define sz(c) ((long long)((c).size()))
  9. #define phb push_back
  10. #define ppb pop_back
  11. #define phf push_front
  12. #define ppf pop_front
  13.  
  14. using namespace __gnu_pbds;
  15. using namespace std;
  16.  
  17. #define int ll
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21. typedef pair<int, int> pii;
  22. typedef pair<ll, ll> pll;
  23.  
  24. template
  25. <
  26.      class key,
  27.      class val = null_type,
  28.      class comp = less<key>
  29.      >
  30. using ord_set = tree
  31.                 <
  32.                 key,
  33.                 val,
  34.                 comp,
  35.                 rb_tree_tag,
  36.                 tree_order_statistics_node_update
  37.                 >;
  38.  
  39. const int N = 2e6 + 100;
  40.  
  41. int a[N];
  42.  
  43. signed main()
  44. {
  45.      ios_base::sync_with_stdio(false);
  46.      cin.tie(NULL);
  47.      cout.tie(NULL);
  48. #ifndef ONLINE_JUDGE
  49.      freopen("input.txt",  "r",  stdin);
  50.      freopen("output.txt", "w", stdout);
  51. #endif
  52.      int n, k;
  53.      cin >> n >> k;
  54.      for (int i = 0; i < n; i++)
  55.           cin >> a[i];
  56.      int prev_best_sum = 0,
  57.          prev_best_ind = -1e9,
  58.          prev_sec_sum = 0;
  59.      for (int i = 0; i < (n + k - 1) / k; i++)
  60.      {
  61.           int cur_best_sum = prev_best_sum,
  62.               cur_best_ind = prev_best_ind,
  63.               cur_sec_sum = prev_sec_sum;
  64.           for (int j = i * k; j < (i + 1)*k; j++)
  65.           {
  66.                int sum = prev_sec_sum + a[j];
  67.                if (j - prev_best_ind != k)
  68.                     sum = prev_best_sum + a[j];
  69.                if (sum > cur_best_sum)
  70.                     cur_sec_sum = cur_best_sum,
  71.                     cur_best_sum = sum,
  72.                     cur_best_ind = j;
  73.                else if (sum > cur_sec_sum)
  74.                     cur_sec_sum = sum;
  75.           }
  76.           prev_best_sum = cur_best_sum,
  77.           prev_best_ind = cur_best_ind,
  78.           prev_sec_sum = cur_sec_sum;
  79.      }
  80.      cout << prev_best_sum << "\n";
  81. }
Time limit exceeded #stdin #stdout 5s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZaVu1v
language:
C++14 (clang 8.0)
created:
6 years 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!