fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "test"
  5.  
  6. #define int long long
  7. #define fi first
  8. #define sc second
  9. #define ii pair <int, int>
  10.  
  11. #define rep(i,s,e) for (int i = (s), _e = (e); i <= _e; i++)
  12. #define reo(i,s,e) for (int i = (s), _e = (e); i >= _e; i--)
  13.  
  14. const int maxn = 3005;
  15. const int mod = (int)1e9 + 7;
  16. const int inf = (int)1e18;
  17.  
  18. int n, k;
  19. int a[maxn];
  20.  
  21. int cost (int l, int mid, int r)
  22. {
  23.     return (a[mid] - a[l - 1]) * (a[r] - a[mid]);
  24. }
  25.  
  26. bool maximize (int &a, int b)
  27. {
  28.     if (a >= b) return false;
  29.     a = b;
  30.     return true;
  31. }
  32.  
  33. namespace sub1
  34. {
  35.     const int maxn = 305;
  36.     int ans, dp[maxn][maxn];
  37.  
  38.     void process ()
  39.     {
  40.         rep (p, 1, k) rep (i, 1, n) rep (j, 1, i - 1)
  41.             maximize(dp[p][i], dp[p - 1][j] + cost(j, i - 1, n));
  42.         rep (i, 1, n) maximize(ans, dp[k][i]);
  43.         cout << ans << '\n';
  44.     }
  45. }
  46.  
  47. namespace sub2
  48. {
  49.     vector <int> dp1, dp2;
  50.  
  51.     void dac (int l = 1, int r = n, int optl = 1, int optr = n)
  52.     {
  53.         if (l > r) return ;
  54.         int mid = l + r >> 1;
  55.  
  56.         int opt = 0;
  57.  
  58.         rep (i, optl, min(optr, mid - 1))
  59.             if (maximize(dp1[mid], dp2[i] + cost(i, mid - 1, n)))
  60.                 opt = i;
  61.  
  62.         dac(l, mid - 1, optl, opt);
  63.         dac(mid + 1, r, opt, optr);
  64.     }
  65.  
  66.     void process ()
  67.     {
  68.         dp1.resize(n + 5), dp2.resize(n + 5);
  69.         rep (i, 1, n) dp2[i] = cost(1, i - 1, n);
  70.  
  71.         rep (i, 2, k)
  72.         {
  73.             dac();
  74.             dp2 = dp1;
  75.         }
  76.  
  77.         int ans = 0;
  78.         rep (i, 1, n) maximize(ans, dp1[i]);
  79.         cout << ans;
  80.     }
  81. }
  82.  
  83. signed main ()
  84. {
  85.     cin.tie(0)->sync_with_stdio(false);
  86.     #ifndef ONLINE_JUDGE
  87.     freopen(TASK".inp","r",stdin);
  88.     freopen(TASK".out","w",stdout);
  89.     #endif
  90.  
  91.     cin >> n >> k;
  92.     rep (i, 1, n)
  93.     {
  94.         cin >> a[i];
  95.         a[i] += a[i - 1];
  96.     }
  97.  
  98.     if (n <= 300) sub1::process();
  99.     else sub2::process();
  100.  
  101.     return 0;
  102. }
  103.  
  104.  
  105.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/re8Bee
language:
C++14 (gcc 8.3)
created:
11 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!