fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long oo = 1e18 + 7;
  4. int n, k;
  5. long long a[1005];
  6.  
  7. namespace sub1 {
  8.  
  9.     long long pre[1005];
  10.  
  11.     void SOLVE() {
  12.  
  13.         long long ans = oo;
  14.         for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
  15.         for (int l = 1; l <= n; l++) {
  16.             for (int r = l; r <= n; r++) {
  17.                 long long res1 = pre[r] - pre[l - 1];
  18.                 long long res2 = pre[n] - res1;
  19.                 ans = min(ans, res1 * res1 + res2 * res2);
  20.             }
  21.         }
  22.  
  23.         cout << ans << '\n';
  24.  
  25.     }
  26.  
  27. }
  28.  
  29. namespace sub2345 {
  30.  
  31.     int pos[505];
  32.     long long pre[505];
  33.     long long dp[505][505];
  34.  
  35.     long long bp(long long sum) {
  36.         return sum * sum;
  37.     }
  38.  
  39.     long long solve() {
  40.         for (int i = 0; i <= n; i++)
  41.         for (int j = 0; j <= k; j++) dp[i][j] = oo;
  42.         for (int i = 0; i <= k; i++) pos[i] = 0;
  43.         dp[0][0] = 0;
  44.         for (int i = 1; i <= n; i++) {
  45.             for (int j = 1; j <= min(i, k); j++) {
  46.                 while (pos[j - 1] + 1 <= i - 1 && dp[pos[j - 1]][j - 1] + bp(pre[i] - pre[pos[j - 1]]) >= dp[pos[j - 1] + 1][j - 1] + bp(pre[i] - pre[pos[j - 1] + 1])) pos[j - 1]++;
  47.                 dp[i][j] = min(dp[i][j], dp[pos[j - 1]][j - 1] + bp(pre[i] - pre[pos[j - 1]]));
  48.             }
  49.         }
  50.         return dp[n][k];
  51.     }
  52.  
  53.     void SOLVE() {
  54.  
  55.         long long ans = oo;
  56.         for (int i = 1; i <= n; i++) {
  57.             a[0] = a[1];
  58.             for (int j = 1; j < n; j++) a[j] = a[j + 1];
  59.             a[n] = a[0];
  60.             for (int j = 1; j <= n; j++) pre[j] = pre[j - 1] + a[j];
  61.             ans = min(ans, solve());
  62.         }
  63.  
  64.         cout << ans << '\n';
  65.  
  66.     }
  67.  
  68. }
  69.  
  70. main() {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(0); cout.tie(0);
  73.     cin >> n >> k;
  74.     for (int i = 1; i <= n; i++) cin >> a[i];
  75.  
  76.     if (k == 2) sub1::SOLVE();
  77.     else sub2345::SOLVE();
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/DkE4Ih
language:
C++14 (gcc 8.3)
created:
7 hours 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!