fork download
copy 
  1. // #pragma GCC optimize("O3,unroll-loops")
  2. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. // __builtin_popcount
  6. // __builtin_ctz
  7. #define int long long
  8. #define pii pair<int, int>
  9. #define duoble long double
  10. #define endl '\n'
  11. #define fi first
  12. #define se second
  13. #define mapa make_pair
  14. #define pushb push_back
  15. #define pushf push_front
  16. #define popb pop_back
  17. #define popf pop_front
  18. #define o_ ordered_
  19. #define ins insert
  20. #define era erase
  21. #define pqueue priority_queue
  22. #define minele min_element
  23. #define maxele max_element
  24. #define lb lower_bound // >=
  25. #define ub upper_bound // >
  26. #define debug cout << "NO ERROR", exit(0)
  27. #define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28. #define MASK(i) (1LL << (i))
  29. #define BIT(x, i) (((x) >> (i)) & 1)
  30. #define ALL(v) v.begin(), v.end()
  31. #define SZ(v) (int)v.size()
  32. #define sqr(x) ((x) * (x))
  33.  
  34. template<class X, class Y>
  35.     bool minimize(X &x, const Y &y) {
  36.         if (x > y) {
  37.             x = y;
  38.             return true;
  39.         }
  40.         return false;
  41.     }
  42. template<class X, class Y>
  43.     bool maximize(X &x, const Y &y) {
  44.         if (x < y) {
  45.             x = y;
  46.             return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  52.  
  53. int Rand(const int &l, const int &r) {
  54.     assert(l <= r);
  55.     int sz = (r - l + 1);
  56.     return l + rd() % sz;
  57. }
  58.  
  59.  
  60. const int MOD = 1e9 + 7; //998244353;
  61. const int LOG = 18;
  62. const int INF = 1e10 + 7;
  63. const int d4x[4] = {-1, 1, 0, 0};
  64. const int d4y[4] = {0, 0, 1, -1};
  65. const char c4[4] = {'U', 'D', 'R', 'L'};
  66. const int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  67. const int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  68.  
  69.  
  70.  
  71.  
  72. // #define LENGTH 1000005
  73. // #define NMOD 2
  74. // #define BASE 256
  75. // const int HashMod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};
  76.  
  77. // #include <ext/pb_ds/assoc_container.hpp>
  78. // #include <ext/pb_ds/tree_policy.hpp>
  79. // using namespace __gnu_pbds;
  80. // #define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
  81. // *(s.find_by_order(2)) : 3rd element in the set i.e. 6
  82. // s.order_of_key(25) : Count of elements strictly smaller than 25 is 4
  83.  
  84.  
  85.  
  86.  
  87. /* Listen music of IU before enjoy my code */
  88.  
  89. const int LimN = 4e5 + 5;
  90.  
  91. int n, k, ans, c[LimN];
  92.  
  93. int dp[LimN], sum[LimN], pref[LimN];
  94.  
  95. void solve() {
  96.  
  97.  
  98.     // dp[i]: tổng số rượu lớn nhất kết thúc tại i (bắt buộc là phải uống thằng i)
  99.  
  100.     cin >> n >> k;
  101.  
  102.     for (int i = 1; i <= n; i++) cin >> c[i];
  103.     for (int i = 1; i <= n; i++) {
  104.         sum[i] = sum[i - 1] + c[i];
  105.     }
  106.  
  107.     for (int i = 1; i <= n; i++) {
  108.         // cần tính dp[i]
  109.  
  110.  
  111.         for (int j = max(i - k + 2, 1LL); j <= i; j++) {
  112.             // các bạn có thể uống từ j tới i 
  113.  
  114.             int sta = j - 2;
  115.             if (sta < 0) sta = 0;
  116.             else sta = pref[sta];
  117.  
  118.             dp[i] = max(dp[i], sta + (sum[i] - sum[j - 1]));
  119.  
  120.         }
  121.  
  122.         pref[i] = max(pref[i - 1], dp[i]);        
  123.  
  124.     }
  125.  
  126.     cout << pref[n] << endl;
  127.  
  128.  
  129.  
  130.  
  131.  
  132. }
  133.  
  134.  
  135. /* Authors: Nguyen Minh Huy from Le Quy Don high school for Gifted Students Da Nang */
  136.  
  137.  
  138.  
  139. signed main() {
  140.  
  141.     #ifndef ONLINE_JUDGE
  142.     freopen("ab.inp", "r", stdin);
  143.     freopen("ab.out", "w", stdout);
  144.     #else
  145.     // freopen("task.inp", "r", stdin);
  146.     // freopen("task.out", "w", stdout);
  147.     #endif
  148.     FAST;
  149.     bool TestCase = 0;
  150.     int NumTest = 1;
  151.     //cin >> NumTest;
  152.     for (int i = 1; i <= NumTest; i++) {
  153.         if (TestCase) cout << "Case" << " " << i << ": ";
  154.         solve();
  155.     }
  156.  
  157. }
  158.  
  159.  
  160.  
  161.  
Success #stdin #stdout 0s 5612KB
comments (?)
stdin
copy 
4 2
7 1 2 4
stdout
copy 
11
https://ideone.com/IaH4tE
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!