fork download
copy 
  1. // Bai 5
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int MAX_N = 3000;
  8. const int MAX_LINE = 3000;
  9. const int MOD = 1e9 + 7;
  10. const ll INF = 1e18;
  11.  
  12. template <class X, class Y>
  13. bool minimize(X &x, const Y &y) {
  14.     if (x <= y) return false;
  15.     x = y;
  16.     return true;
  17. };
  18.  
  19. struct Line {
  20.     ll a, b;
  21.  
  22.     Line() {};
  23.     Line(ll a, ll b) : a(a), b(b) {};
  24.  
  25.     ll eval(ll x) { return a * x + b; };
  26.  
  27.     double intersect(const Line &other) const {
  28.         return (double)(other.b - b) / (a - other.a);
  29.     };
  30. };
  31.  
  32. struct ConvexHullTrick {
  33.     Line line[MAX_LINE + 5];
  34.     int ptr, sz;
  35.  
  36.     void addLine(const Line &newLine) {
  37.         while (sz > 1 && line[sz - 2].intersect(newLine) <= line[sz - 2].intersect(line[sz - 1])) sz--;
  38.         line[sz++] = newLine;
  39.         if (ptr >= sz) ptr = max(0, sz - 1);
  40.     };
  41.  
  42.     ll query(ll x) {
  43.         while (ptr + 1 < sz && line[ptr].eval(x) >= line[ptr + 1].eval(x)) ptr++;
  44.         return line[ptr].eval(x);
  45.     };
  46.  
  47.     void reset() { ptr = sz = 0; };
  48.     ConvexHullTrick() { reset(); };
  49. };
  50.  
  51. int n, k;
  52. int a[MAX_N + 5];
  53.  
  54. ll sqr(ll x) {
  55.     return x * x;
  56. };
  57.  
  58. namespace SUBTASK_1 {
  59.     const int N = MAX_N;
  60.     const int K = 2;
  61.  
  62.     void Solve() {
  63.         ll total = 0;
  64.         for (int i = 1; i <= n; i++) total += a[i];
  65.  
  66.         ll res = INF;
  67.         for (int l = 1; l <= n; l++) {
  68.             ll sum = 0;
  69.             for (int r = l; r <= n; r++) {
  70.                 sum += a[r];
  71.                 minimize(res, sqr(sum) + sqr(total - sum));
  72.             };
  73.         };
  74.  
  75.         cout << res << '\n';
  76.     };
  77. };  // namespace SUBTASK_1
  78.  
  79. namespace SUBTASK_3 {
  80.     const int N = 300;
  81.  
  82.     ll dp[N + 5][N + 5];
  83.     int b[N + 5];
  84.  
  85.     ll DP(int b[]) {
  86.         for (int i = 0; i <= k; i++) {
  87.             for (int j = 0; j <= n; j++) {
  88.                 dp[i][j] = INF;
  89.             };
  90.         };
  91.  
  92.         dp[0][0] = 0;
  93.  
  94.         for (int i = 1; i <= k; i++) {
  95.             for (int r = i; r <= n; r++) {
  96.                 ll sum = 0;
  97.                 for (int l = r; l >= i; l--) {
  98.                     sum += b[l];
  99.                     minimize(dp[i][r], dp[i - 1][l - 1] + sqr(sum));
  100.                 };
  101.             };
  102.         };
  103.  
  104.         return dp[k][n];
  105.     };
  106.  
  107.     void Solve() {
  108.         ll res = INF;
  109.         for (int startAt = 1; startAt <= n; startAt++) {
  110.             for (int i = startAt; i <= startAt + n - 1; i++)
  111.                 b[i - startAt + 1] = a[i];
  112.             minimize(res, DP(b));
  113.         };
  114.         cout << res << '\n';
  115.     };
  116. };  // namespace SUBTASK_3
  117.  
  118. namespace SUBTASK_5 {
  119.     const int N = 500;
  120.  
  121.     ConvexHullTrick cht;
  122.     ll dp[N + 5][N + 5];
  123.     ll pref[N + 5];
  124.  
  125.     ll DP(ll pref[]) {
  126.         for (int i = 0; i <= k; i++) {
  127.             for (int j = 0; j <= n; j++) {
  128.                 dp[i][j] = INF;
  129.             };
  130.         };
  131.  
  132.         dp[0][0] = 0;
  133.  
  134.         for (int i = 1; i <= k; i++) {
  135.             cht.reset();
  136.             for (int r = i; r <= n; r++) {
  137.                 ll a = pref[r - 1] * -2;
  138.                 ll b = dp[i - 1][r - 1] + sqr(pref[r - 1]);
  139.                 cht.addLine(Line(a, b));
  140.  
  141.                 dp[i][r] = cht.query(pref[r]) + sqr(pref[r]);
  142.             };
  143.         };
  144.  
  145.         return dp[k][n];
  146.     };
  147.  
  148.     void Solve() {
  149.         ll res = INF;
  150.         for (int startAt = 1; startAt <= n; startAt++) {
  151.             pref[1] = a[startAt];
  152.             for (int i = startAt + 1; i <= startAt + n - 1; i++)
  153.                 pref[i - startAt + 1] = pref[i - startAt] + a[i];
  154.             minimize(res, DP(pref));
  155.         };
  156.         cout << res << '\n';
  157.     };
  158. };  // namespace SUBTASK_5
  159.  
  160. int main() {
  161.     ios_base::sync_with_stdio(0);
  162.     cin.tie(0);
  163.     if (fopen("MAIN.INP", "r")) {
  164.         freopen("MAIN.INP", "r", stdin);
  165.         freopen("MAIN.OUT", "w", stdout);
  166.     };
  167.  
  168.     cin >> n >> k;
  169.     for (int i = 1; i <= n; i++) {
  170.         cin >> a[i];
  171.         a[i + n] = a[i];
  172.     };
  173.  
  174.     if (k == 2)
  175.         return SUBTASK_1::Solve(), 0;
  176.     if (n <= 100 && k <= 100)
  177.         return SUBTASK_3::Solve(), 0;
  178.     SUBTASK_5::Solve();
  179. };
  180.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/rAx9tb
language:
C++14 (gcc 8.3)
created:
2 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!